I certainly wouldn't have a page with a million links on it! If I remember right, the limit on XML sitemaps is 50k URLs or 10MB filesize.
I'm making assumptions here, but I reckon there are only two reasons you might be considering a sitemap here:
- A sitemap for improved usability. In which case, you need a substantially pared-down version, and you do not need a sitemap that links to all of your pages. It should allow visitors to easily find the appropriate site section for them, and then once they've reached it your navigation does the work
- A sitemap to try to get pages indexed. IMO a sitemap is not a solution to spidering problems. If you have such problems, work on internal navigation instead.
I would suggest both examples point at a similar solution - a stripped down sitemap that links to major sections (perhaps use Google's old school limit of 100 links/page maximum as a guide) and solid internal navigation that works for both spiders and visitors.
