Mobile ad hoc networks require routing algorithms that provide high performance in terms of delivery times of packets for dynamically changing topologies under various load conditions. A routing algorithm is proposed which is based on adaptive Q-routing technique with Full Echo extension. The proposed algorithm, called Adaptive Q-routing with Random Echo and Route Memory (AQRERM), has the improved performance in terms of overshoot and settling time of the learning. It also greatly improves stability of routing under conditions of high load for the benchmark example.