I rode from Flagstaff to Payson on the Lake Mary Road and AZ-87 about 6 years ago. I don't recall the traffic being a problem. Of course, I was going downhill on AZ-87.
Some alternative routes:
Payson to Flagstaff: From Payson, take AZ-260 northeast to the gravel road along the Mogollon Rim(General Crook Trail). Ride that west about 20 miles to AZ-87, then go north to Lake Mary Road to Flagstaff.
Prescott to Flagstaff: Take AZ-89 north to Ash Fork (a nice scenic ride through Chino Valley and Hell Canyon). Ride the I-40 shoulder 21 miles east to Exit 167 just east of Williams (you can miss 4 miles of I-40 by riding through Williams on Business I-40). From Exit 167, ride old Route 66 roads to Flagstaff. Route 66 websites give detailed directions and historical information on that section. There were short stretches of gravel and rough pavement on old Route 66 roads, but a touring bike handled them fine.
Prescott to Wickenburg: The first part is not difficult-riding mountainous, wooded terrain, changing to open areas around Peoples Valley. A long, screaming downgrade south of Yarnell to the desert.
Wickenburg to Gila Bend: Continue the above route by taking the Vulture Mine Road south out of Wickenburg (some maps incorrectly show it as unpaved). It's a beautiful Senora Desert route with virtually no traffic (and no services or anything else) to I-10. Especially nice in the early spring when everything is booming. Cross I-10, go through Wintersburg to Old Highway 87, going through Arlington. That's another very low-traffic, paved road. Due to summer heat, I'd skip this route in the summer.
