The problem your going to have is that there is currently no search functionality for pulling up a list with a limit of 5,000 people...it's easy for a developer to do on the back-end in SQL, but not on the front-end. What I would do is create 2 groups (group A and group

I would first limit my results to only contacts who have data in their email address field, then I would just search for everyone who's last name starts with "A", and add them to group A, last name starts with "B", add them to group A, and so on until you get about 5,000, then dump everyone else (contacts who are not in group A) into group B. Not pretty, but it is doable. That's how I would do it in my database, you may have other criteria other than last name that would make more sense when segmenting your database. Hope that helps.
You could also set up a round robin and evenly distribute your list between 2 users ...that would actually be pretty fast