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:
4Q FJ 123 679
4Q FJ 123 677
4Q FJ 124 678
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.