Arizona (397 mi): US 89 from Mexico to Florence Jct 148; US 60 to Pineyon 141; AZ 61 to St Johns 33; US 666 to New Mexico
New Mexico (129 mi): US 666 to Colorado
Colorado (436 mi): US 666 to Cortez; US 160 to Durango; US 550 to Montrose; US 50 to Grand Junction; US 6-24 to Rifle; CO 13 to Wyoming
Wyoming (421 mi): WY 330 to Creston; US 30 to Rawlins; US 287 to Lander; WY 320 to Riverton; US 26 to Shoshoni; US 20 to Greybull; US 310 to Montana
Montana (425 mi): US 310 to Laurel; US 10-12 to Billings; US 87 to Great Falls; US 91 to Canada;
Total: 1808 miles

US 789's routing would've been almost 200 miles longer than using US 89 and US 91 to go from Nogales to Sweetgrass.
There is a June 1950 memo from Wyoming to AASHO floating US 777 as the designation for this route. AASHO pointed out that since the route was between US 87 and US 89 it should get a "...3-digit number more fitting such as 387 or 787"
An October 1952 telegram from AASHO noted that the route would be largely concurrent with other US routes and that the states involved did not provide sufficient data to justify.
There seems to be very few documents in the AASHO database on US 789, though the ones that are there reference other documents.
Per research done by aaroads.com, the proposed route became the Canada to Mexico Highway. The states then all signed it as state route 789, which appeared on respective state official maps in 1954 and 1955. By the mid-1960s, both Arizona and New Mexico dropped the route. Montana dropped it in 1972-73 and Colorado in 1983. Wyoming continues to sign it to this day along the entire 1954 routing, even though it is cosigned with other US routes on over half of it.
Note that the proposed US 789 from Cortez CO to Canada was already rejected as an extension to US 666 in 1939.