LiPo are more like 4.2V when fully charged and 3.7V when discharged.
If you running at 16MHz, then full performance is guaranteed down to ~3.8V.
If you run at 8 MHz, it's less. So you coul run from a LiPo directly and not use a regulator at all.
I have an RF remote control that does just that - 8 MHz, 1000mAH LiPo, MAX1811 to control recharging the battery from a 5V source.
I am testing a '2560 design right now using 3 AA batteries. I have a 24V to 5V DC/DC module on the board, but don't have the right female cables yet to power it up.
Running from battery with no regulator is fine as long as the battery voltage is in the correct range.