Esp8266-01 AT commands returns random chars and/or "ERROR"
The problem is mainly in using Serial and SoftwareSerial together. Or it can be due the esp getting less current than it requires from the Arduino(you are also damaging your Arduino!), use an external 5V source (I use my computer USB)

Why dont you directly use Serial for communication with pins 0 and 1. Just upload a blank sketch, connect Arduino Tx, Rx to esp's Tx, Rx(reverse Tx, Rx if not working). What you type into Serial will then be sent to the esp. Later if you wish to communicate to esp in sketches, use only SoftwareSerial. 

Also, the esp is not 5V tolerant so you need to use a level shifter(like the cd4050 ic) or a voltage divider(less efficient) for signals from the Arduino to the esp. 3.3V is considered as a logical HIGH so you dont need to do any changes for signals from esp to the Arduino.

I highly recommend getting a USB TTL converter, this will save you a lot of headaches and debugging will be easy. I did things without it for 1-2months and now I can totally feel the difference.