Illustrator has a feature called Artboards that are kind of like tiles. You could jut them up against each other in a mockup of your tile layout, and then do your illustration and layout within those "tiles" to get a really good feel for what you're doing and see it in a very good rendition of how it's going to come out once on the device in the tiles.
[EDIT: Addition] One other great feature of Artboards for this is the
ability to quickly duplicate and move them around, so you could really
check how things line up with one another on all sorts of different
tiles, really easily. As far as I know, though, there's no
"instancing" of Artboards so that you can edit one and have it
propagate changes to other instances of that artboard. Although
Illustrator does have Symbols, which you could use to get instance
Photoshop has Slices, which could also be used for this process, in much the same way, but the way it handles really big files (in terms of dimensions and layers) is going to get a little unwieldy if you start working on a big map.
And Illustrator has a good command of both bitmaps and vector graphics, so it's the preferable choice, I'd suggest. But you will need to learn the ways of antiquated software interfaces. Fun Fun FUN!