Evidence indicates that waves as tall as skyscrapers and thousands of kilometers wide once washed over the Red Planet.