Custom pagination generates title 404

Using query_posts is generally not recommended. Looking at the Codex, it specifically states:

Note: This function isn’t meant to be used by plugins or themes. As
explained later, there are better, more performant options to alter
the main query. query_posts() is overly simplistic and problematic way
to modify main query of a page by replacing it with new instance of
the query. It is inefficient (re-runs SQL queries) and will outright
fail in some circumstances (especially often when dealing with posts
pagination). Any modern WP code should use more reliable methods, like
making use of pre_get_posts hook, for this purpose.

Note the “especially often when dealing with posts pagination” part.

I would try re-writing your code with one of the other suggested methods and see if that changes the behavior.