You could make 2 categories of terrain: underground and surface. Units need a promotion (which is inherent in their homeland, eg: svartalfar could have inherent underground promotion) in order to move into these 2 kinds of terrains.
yes, promotions to move underground is a good idea. there could also be races with half/double movement underground.
you'd still need tunnels or gateways to the underground world. serving as chokepoints between the two worlds.
then split the world into two sections (one can be graphically located next to the other with inpassible barrier between them).
I guess you could then design a terrain feature across 2 blocks in both underground and aboveground, like a stairway. eg over the tiles A(M,N+1) and A(M,N) and then also underground in corresponding place a stairway will automatically appear across U(M,N+1) and U(M,N)
then in the above ground world when moving south from A(M,N+1) it is considered adjacent to underground tile U(M,N). and when in U(M,N) the tile adjacent to the north is considered A(M,N+1).
the main thing is to get it to work seemlessly in the AI path routing algorythms, much in the same way as the AI can go west from tile reference (0,N) to the other side of the world (M_max,N) when the world wraps around.
i wrote this as above ground A(M,N) and underground U(M,N), and it could be represented as side by side, or as two different views. then in the map saved file nothing special has to happen, just reference the underground coordinate system according to the above ground coordinate system so U(M,N) becomes plot(M+map_width/2,N). so in the map file it doesn't need to consider two different worlds, and just store the plot information as normal.