Silly question. Do you have the VS pin (pin 10) of the L293D parts connected directly to the battery? Or is it connected to the 5V supply? That pin supplies the voltage that actually drives the motors and should not be going through the regulator.