My understanding is that the Arduino is limited to driving the stepper about 300 RPM. Don't know if you can do better than that with the Mega, it's faster than the Uno that that information was good for. You may have to modify the current code that's available for stepper driving to get the speed you want. My understanding is that the overhead of running the Arduino translator on the chip is what causes the low speed. That's not noticeable until you start doing some very time sensitive things, like bit banging a 48 kHz signal while your also trying to read inputs, count and store steps and calculate what frequency you would like to be putting out.
I wrote the program myself and I didn't find that to be the case. The physical limitations of the motor and driver were the gooseneck. I remember that 1/4 stepping it and sending a pulse every 60 micro seconds to get it up a little over 1200 RPM. The motor would start stalling much higher than that.
The program was simple, it had a while loop that would check the status of a button, if it was pressed, it sent a pulse to the driver by switching a pin from high to low, then looping back to see if the button was still pressed. I recall running a test to output the length of time for each loop, and it was in the region of 10 microseconds which means in theory, if the stepper were physically capable of it, the arduino could send it to about 7500 RPM.