[PvK]

You can make him a magic carpet, or conquer the intervening sea and then have him cross underwater using a simple water-breathing item. I think Faerun has a number of amphibious provinces which your sailing armies should be able to acquire. Not to mention mercenaries and other ways to attack underwater.

PvK