To get more torque, you need to drive the stepper from a higher voltage, as Mike says. You're driving it from a 9v adapter, and the L293D is probably dropping around 2V (maybe even 3V). So even if the supply is maintaining 9V output under load, the motor will be getting around 7v when it is designed for 12v.
To get it to step reliably at higher speeds, you need to either increase the voltage to get more torque, or change the code to accelerate and decelerate the motor more gradually, instead of trying to go immediately from stationary to full speed.