Whilst I don't expect to have quite the same issue as you, as I'm building into an existing landmass so I can account for such issues, I still think free-foot travel will be an issue due to the sheer size of the world. To combat this, I'm planning on implementing a node-based travel system akin to Morrowind.
I'll have ships, small boats, Mage Guild teleportation and cart as my core fast travel types.
You won't be able to get from one place to another directly, even by the same means (e.g. from Khuul to Vos directly in the image below), you'll have to go through the nearest node/s (e.g. Khuul, Dagon Fel, Tel Mora, Vos).
As some cities and locations will have more than one transport type, the world is linked up in an interesting way as you may hop between different transport types and different nodes to find the most efficient path (e.g. if you're inland, you might go cart to a city, Mage's Guild teleportation to another city that is near the ocean, then boat to an island). Nearest won't always be most efficient, as different travel types will have different costs, so you may either opt for '# of hop' efficiency (lowest number of hops), 'cost to location' efficiency (more hops, but a cheaper trip end-to-end) or some middle-ground in-between.
I'm sitting at 3500x3500, which goes to the border of the shape, but I've got a lot of ocean.
I actually think mine might be bigger (though obviously very sparse at the moment). My image is from the mini-map, but I think Bahamut's is at 4% zoom level.
EDIT:
Actually, I think mine is a bit smaller - Bahamut's definitely got more going on vertically.
I think I'll end up with more pathable tiles though, even once mountains and structures start eating away at the current count from the grassy landmass - as I haven't even started the subterranean levels yet!
Here's what I could I could fit into a single screenshot at 4% zoom. I'm assuming Bahamut took multiple screenshots and stitched them together.