How does WordPress determine if a paged query var is too high?

A query either returns posts or it doesn’t. Whether it’s a non-existent page number, a non-existent category name, a non-existent post name, etc., it’s all the same.

The rewrite rules is matched, which populates the query vars, which forms the query. The query is sent to the database, and the database returns some amount of posts between zero and whatever number was requested.

The only difference between all of those cases is what it does after it’s determined to be a 404, which depends on what rewrite rule was matched. In the case that the name query var is populated, it tries to find the closest match with an additional LIKE query, and redirects there if something is found.