First off, this will probably do best to a map made from scratch. I'm using Photoshop at 1.8 Ghz with 512 MB DDR.
To get an overview of my new world, I created an image with the same size of the world (18944x7296), but in bitmap or 2-color indexed to save memory (2,56 MB for me), preferably saved in .psd or any format allowing guidelines.
Then I did the world division and I found that squares of 2432 px was both good, sufficient and fully workable (divided the map into three rows). No borders and no overlapping with neighbouring areas (I tried that but prefer this).
To get provinces right between areas, either base it on the overview-image or an example of when you've completed the upper left area and want to continue on the one below.
Expand the height (upper only) on the area below, paste the lower parts of the first area, do the painting on the area below and when you have a smooth enough provinces, contract the image to get the usual 2432x2432.
And this is only how I do it... hope it helped.