The Arduino Mega already has its own voltage regulator, you could attach your battery pack directly to the VIN pin, or the barrel jack.
You're also using a 12V source to get 5V, meaning that you're throwing away more than half of the power you use, as heat. You may want to find a battery holder that gets you 7.5V or 9V, closer to the desired voltage but with enough headroom for the regulator dropout.
Glad you're trying things before asking, though. A lot of people get hung up asking questions before they do every little thing, and as a result their progress is extremely slow.