I'll add the technique I use in Gimp, as it may have an equivalent in photoshop, plus turn this into a mini tutorial. The basic idea is to use a checkerboard grid with a layer mask, plus some strokes. This also assumes you do not want to cover any of the existing map.
1- Decide on the width you want for the lines, and enlarge the canvas to that size. i.e. for a 1200x800 map you might want a neatline 20 px wide, so make the canvas 1240x840, centering the layers.
2- decide on a the number of segments you want. Keep it close to the same proportion as the image size so they stay square. For example, say 31x21 in this case. Using an odd number will ensure the same colour in all four corners.
3 - create a new layer this size.
4 - filters->render->pattern->checkboard, and select a value of 1 (pixel) The checkerboard is in your fg/bg colour.
5 - scale the layer to the image size, with NO interpolation (this is the magic step that takes care of the nasty math!)
6 - use the move tool to place it over the whole image.
7 - create a selection bordering the area. Select->all, select->border 20 (the size we wanted)
8 - add a layer mask, using the selection.
9 - If you want to outline the checkboard in a different colour, use the select by colour tool and click on the colour, then stroke the selection with an even sized stroke.
10 - Turn the layer mask into a selection and stroke the selection again, using a 2x the width in step 9.
11 - add more borders, etc.
Here is the result of this: