Thinking about the new Gondor map, what if it is just a reverse version of "March of the King", with South Ithilien instead of North Ithilien?
It could have us starting from Minas Tirith, going through South Ithilien, and finding the main road into Harad still blocked. We would circle back around to the port of Harlond, and use boats there to travel to Umbar by sea. IIRC Harlond is where Aragon docked the Umbar ships he used to attack with, so they still should be there unless they sunk them all for no reason. Using the captured Umbar ships to sail back to Umbar in some sort of disguise could make sense.
Then after arriving in Umbar, and doing whatever we need to do there, we make our way back north by land coming up into Harondor and connecting back to South Ithilien.
I don't get why people panic what we don't have enough size on world map. In last 5 years, SSG already replace region maps like Gondor, Rohan, Eriador. Gondor region map don't have place for Umbar? Ok, how about Mordor region map? They need change it anyway when we reach Rhun, Nurn or other parts of Mordor