How to calculating requirements of power supply for a project
A power supply a 9V battery is not. Since you are using batteries the L293D is a very poor choice for a driver, it uses silicon transistors which I believe are in a darlington configuration which will cause a voltage drop of from 1.4 to 2.8 volt on the motor.  The 4 (or more) AA batteries will work but use a MOSFET bridge. You can always use a small SEPIC (Buck/Boost) converter to power it, that will keep the voltage constant until the batteries are exhausted. Set it to about 9V and power the arduino via the VIN input for more filtering. You will need a way of measuring voltage. You will lose less power with the converter then you are losing in your current driver.