Use side warps between DMaps.
So, create a DMap for every palette you want to use, and set the actual map number in that DMap to 1 (or whatever your overworld map is). You'll end up with a variety of different DMaps that have different palettes under the Appearance tab, but all use the same map number under the Mechanics tab.
Then use the side warp menu (F11) on each transitional screen to set Scrolling Warps between the different DMaps. That way you can have all your overworld screens on a single map, but change colors as you pass between them.
There's also a related quest rule under the Combos rule list called "Scrolling Warps Don't Set The Continue Point" - leave this unchecked if you want the player to restart at the last used scrolling warp, or check it if you want them to restart at the beginning of the overworld (or their last used entrance warp).