The motors run from 9V?
The Mega needs 5V.
Motors can require high surge currents, such as when they stall, that can briefly drag down the voltage and cause the microcontroller to reset. Best way around that is to give the motors and the uC their own source - in this case, 2 regulators in parallel powered by the same battery.
Lots of choices here for 5V the Mega - modify a USB cable and bring 5V in there.
How much 9V current did you need? The pololu selection is kind of limited, these will provide more current.
http://www.mouser.com/Power/DC-DC-Converters/_/N-brvxe?P=1yxt6nq&Keyword=switching+regulator&FS=True
A single resistor is used to set the output voltage, there is a table in the datasheet.