photoshop has a limit of 2 gigs (at least up til CS3 which I use) - I've hit that with my 16000 x 12000 map I'm currently working on, I'm getting around it by flattening stuff and saving as a new file. What are you going to use the maps for, if you're only going to print them on your own printer 200 dpi would be adequate, but if you plan to print professional then go for 300 instead.
Another option is using Illustrator or Inkscape which works in vector and therefor can be scaled up and down without loss/pixelation.
Personally I would work top down, its easier to make the whole continent and make that look good, then divide it up into countries after using the landscape to help decide where the borders go.