I rode through Mescalero last May on my way to Dallas from San Diego. I used US380 to cross Texas, it's a good road throughout most of its entire length, with the exception where it goes through Denton (avoid University drive within the loop if you decide to take this route, use McKinney/Oak to get across this city). It gets pretty remote west of Bridgeport. Stock up on water in Tatum NM, there won't be anything to drink until Roswell.
US70 is awesome through Ruidoso and Mescalero. There are ample shoulders all the way to Las Cruces where you can hook up to the ST or opt for the I-10 corridor.
A few years ago I also rode from Florida to Houston via New Orleans. I used US90, and it was good with some short spotty sections through Mississippi. In downtown N.O., I took the ferry at the end of Canal Street to cross the big river and cruised along the levy pathways to connect back on to US90 towards Lafayette. I continued up to Opelousas and then went on US190 towards the Texas border, which has good shoulders except for a few miles through Kinder (which is not so kind
. I crossed into Texas at Deweyville.
If I were to connect my two tours, I would probably continue on US190 to Jasper, and then head for Lufkin, Tyler, Mineola and then hook up with US380 at Greenville. I would avoid cycling into Dallas/Fort Worth, unless you like bike-averse urban sprawl.