Your analysis is wrong. You are not passing the full set of messages to the paginator.
Querysets are lazy, and are not evaluated into they are iterated: in the case of the paginator, it will slice the object - which results in LIMIT/OFFSET being added to the SQL query before it is sent to the db. No more than a page of results will be fetched.