Hello, good questions! You might be the first person to use all six motor outputs at the same time for an extended duration.
Don't try to connect another 9v power supply. Power supplies don't like to work together, and will actually fight each other if you try to do that. (This is because their desired output voltages will always be slightly off, like if one power supply wants to output 9.01 volts and another wants to output 8.99 volts, they will try to push the combined output voltage closer to each's desired output voltage).
Always power a Bricktronics Megashield using the barrel jack on the shield, not the one on the Arduino Mega. There is only a single pin connecting the motor voltage between the two boards, and to prevent it from melting due to extreme over-current situations, we added a 200 mA auto-reset fuse there. That would explain why it stops working after a while when plugged into the arduino instead of the megashield. The fuse is not part of the power path between the megashield's power socket and the motors, it's only between the arduino mega and the megashield.
I would guess that either your chips are overheating and shutting down, or maybe your power supply isn't able to provide enough current? What is the rating on your 9v wall plug? It should have a current rating in A (amps) or mA (mililamps, thousandths of an amp) on the case. Each motor can draw upwards of 0.8 amps (800 mA)  so you probably want a power supply that can handle at least 4.8 amps, to handle the worst-case power draw. Current used is proportional to how much load is on the motor shaft, so they will use less current when freely spinning (nothing connected) and use a lot of current when they are straining against a load that resists turning (moving heavy objects, etc).
Can you add some Serial.println statements to your Arduino code to check if the processor is still running when the motors stop? They the code is still running when the motors stop, then it's probably an issue with the motor driver chips. Do they end up really hot when the motors cut-out?
If the arduino print statements stop printing out when the motors stop, that probably indicates a power supply problem. Double-check your 9v power supply to see how much current it can supply. If you have a multimeter we can make a slight modification to your power supply cable to be able to monitor how much current is being drawn from the power supply.
I'm sure we'll be able to figure this out.