There are two issues. First is the number of UARTs. Second, the location of the pins of the UARTs.
The Mega boards do have additional UARTs (four in total each). However, when the shield is attached, it uses D0/D1 for the connection between the board and the NBIoT module. Those pins are connected to the first UART (Serial) which is also connected to the USB interface.
The Leonardo might be a good option for this as it has two UARTs, and the one that the shield connects to is separate from the USB interface. (You will need to use Serial1 for communicating with the NBIoT when using the Leonardo.)