Arduino Clock Speed effect on Stepper Speed
Without seeing the rest of your code, the best guess - and I think it is quite likely - is the use of delay() and printing within the stepper function. With 2 motors running, and even ignoring the printing time, there will be a total of 200ms taken up by the delays. That means each motor gets serviced a maximum of 5x/sec. Stop one motor, and the other one can double that to 10x/sec.

Look at the Blink Without Delay example for one way of managing timed events without calling delay(). The SimpleTimer library provides another. 

Update:


  ...run() events are triggered within a while() loop ...


Ah, yes, I see that. So it looks like only one motor could run at a time - the while() loop runs until this motor reaches its target. But you said you run two at a time. So yes, I think understanding the rest of the code will help.