There are a few different ways to manage the ads here.
1. First, theme the groups. If you've managed to get 1mil keywords in an account, then you've used several different theming processes to combine keywords to get there - use the same type of structure to build your ads. Pick the main difference when you combined the keywords, and focus around that for each ad type. It is possible to have 20k keywords do well using the same ad. (Although, there are also management issues of using so many keywords and you really need to use some report/excel combining functions to see how ads are preforming).
2. Another way is to build several ads about your business. Focus on your unique business model. Let's take a test case with Amazon. They might advertise on 1 million keywords, and half of those have one thing in common - media (books/dvds). The other half have something else in common (their partner stores). So taking on a branding type campaign around your product and using several of the same ads in many groups can work, and then custom ads for high priced/high impression groups (depends if you have 1 million KWs because your a shopping mall with 100k products, or of you're managing unique combinations around a single theme). Dynamic insertion can definately be your friend here as well.
3. If your a large company, then hand off themes to the various departments after an AdWords tutorial (this is how a few fortune 500 companies operate). Let them build the campaigns and then go back and fix the issues. Suddenly, this type of advertising campaign is broken down by department and doesn't seem like a monster account, but a lot of sub accounts to manage, which can psychologically make things easier. Just make sure that the departments don't choose the same keywords and start bidding each other up (this has happened before, where it was found that one company had several accounts and the bidding wars were between different departments of the same company). If this is your strategy, make sure there is a centralized person who is keeping tabs across the various accounts.
One of the most important things is not to dwell too much on any one keyword that doesn't get Xk impressions a month (set a target number based on some real data - not hypothetical numbers). Let the keyword stragglers sit in an adgroup and don't worry about them getting disabled, set a threshold for words you will manage - and let the others sort themselves out. Just make sure you don't pick too many unrelated/under preforming keywords that make your account get slowed. Having an account of this size slowed is a lot more work to fix all the problems. If you've created good themes for the keyword groups - then you have the choice to manage ROI by groups and not individual keywords
The most important thing is the organization. If you make too many groups and keywords, you'll just bury yourself in busy work. Use bulk uploads and make excel your friend for managing this account. If you spend enough, your rep won't have any problems sending you excel sheets for when you want to make major changes.
It can also be advantageous to talk to your rep about what you plan on doing, and get your reps input. AWA has mentioned in the past that it is one of his pet peeves for people to upload 500k keywords half of which never get impressions. So don't just surprise your rep with this, but make sure you've had a couple conversations about the project first. Campaigns with 1mil keywords can be very effective - but it takes a lot of upfront planning and organization so you don't get swamped by what sits in front of you.