Tower Pro likely take 6V max. Your voltage regulator should output 6V ideally. However, with a 7.4V LiPo, it’s likely just at the limit of providing 6V - check the dropout voltage.
A 4.8V battery likely won’t burn the MEGA, but it’s not enough to power it. Note too that AA batteries tend not to be able to discharge at a higher current.
Can you provide a photo of the hexapod? Normally these consume high current. It’s not at all designed for a robot - this still still RC servo tech adapted for robotics.
The issue is likely that the servo simply does not have enough torque, and a side issue is that they are power hungry.