I had only one software serial active. Used it for input and output simultaneously, just pumping its input to its own output.
So having the 4 hardware serials on the Mega would surely be (just) enough. On one I would use both input and output, the others are then just used for output only. Hardware support on these port would surely be beneficial to the latency.
I am eyeing the Mega for this project, also because my fear is I will run out of program (and probably ram) memory on the Uno (which I use now). I also saw a memory extension for a good amount of memory and understood from scanning the text, it could also be used for ram. If that is true, my troubles are over
The project also involves a LCD display and some keys.