Given the definition of the MGRS from wikipedia we know that your example 4QFJ123678
can be split up as follows:
4Q
is the Grid Zone (columns in a range of 1-60 and rows in the range C-X omitting I and O). As rows increase go further east, as columns increase go further North.
FJ
is the Grid Square (columns in the range A-Z and rows range A-V, both omitting I and O). Values increase to the East and North.
123 678
is the precision down to the 100 metre square in columns and rows. Values increase to the East and North.
So in the simplest case to get up, down, left, and right you just need to subtract or add from the 100 metre precision rows and columns, thus you get:
- North
4Q FJ 123 679
- South
4Q FJ 123 677
- East
4Q FJ 124 678
- West
4Q FJ 122 678
If you wanted to you could write this into a script pretty easily, but you would have to handle the cases where you cross Grid Squares and Grid Zones.
Also if you use Python might be to look at the Python mgrs library that converts to/from MGRS from latitude/longitude.