So I've been looking at the names of the maps in my saves folder and it looks like the maps are named based on their x / y coordinates on the world grid.
For example, the tile / area you start in at the beginning of the game (eastwillow / Yoma River Valley) is 5050.map, while Port Kuudad is 2 tiles north and 2 tiles east, making the name for that map 5248. The upstairs for houses in Port Kuudad is actually considered an exterior location and is named 5248_up. All interiors are named based on the name of the zone.
I've yet to experiment with the map editor but I'm under the impression one could create new world spaces by making map files with the appropriate names. I'm hoping that as long as the files are created already then the engine would assume you've been there and load the files rather than try to create the files itself from the datapak file and fail. As for custom interiors, I'm not sure how to go about doing this yet. I'm going to guess staircases and the like have scripts that would directly reference the interior cell's name.
It's been a long day and I'm about to go to bed. Testing will have to wait until tomorrow. If this is already common knowledge, ignore everything I just said. I'm new to this game.
Edit: So I fought sleep, downloaded the map editor, and managed to create a 5052.map and traveled to it, whereas the game previously told me there was nothing there and to turn back. YUSSS!!! It appears creating new exterior locations is possible.
Edit 2: I apologize for my excitement, it looks like this is mostly documented already on your website(
http://apocalyptech.com/eschalon/map.php). I'm surprised there aren't more mods for this game, particularly ones that utilize the ability to create new exterior maps.