@ OpenSource: Are you sure about those figures? Did you accidentally include the servo current or some other load in the 500mA you quote for the Mega? I don't have one, but 500mA sounds a bit high.
I don't love the idea of parallel connected batteries- flirting with Murphy's law!
Provided you don't need the supply for the servos & motors to be really stable, I would suggest 4 D size Nicads or NiMH in series ßto run them, and a separate set of 6 AAs for the Mega. Connect the -ve of both sets to ground, of course. You don't need any more regulators with this setup as the Mega has its own.
If you don't want to go rechargeable, the lantern battery is a good option.