Not to be contrary, because I tend to be too often, but the Rio Grande actually starts in Colorado and passes fairly close to Santa Fe. So I guess the assumption is that you mean they start walking near El Paso as opposed to staying on the river, say in a powered boat, which would be easier.

That being said. I lived in New Mexico for several years and traveled to just about every city and town in the state. You will see a lot of this between El Paso and SF:

In the north nearer SF:

And a lot of this in the southern half nearer Las Cruces:

You will also see some strange rock formations, such as Camel Rock just west of Santa Fe:

It is beautiful country and we'd probably still be there or in Colorado if we had not decided to move back to California to be closer to our first grandchild.

Good luck with the story.