The Hayduke is pretty rough requiring caches iirc. The GET seems a bit more doable, though parts of AZ closer to Phoenix would be pretty hot by then (most of AZ is in a low desert while NM is high desert, so the former will be hotter in late spring).
Depending on the weather maybe the AZ line going into the Gila area of the GET. Alternatively taking the CDT from Lordsburg to the Gila and maybe back is something to consider? Not sure if there’s an easy exit going north or east on the CDT/GET going out north of the Gila though.
If next May is warmer, consider an “upper New Mexico loop”