Hi again @bikas,
With the example provided with soft_uart you can get up to 115200 without errors using the WInterrupts.c file I modifiied which is available on this post:
http://forum.arduino.cc/index.php?topic=144446.msg2336042#msg2336042
And using 8E2 (or 8O2). The example is a very simple one, with no other things running, just serial communications. So, surely, you will not get to that baud rate in a more complex application.
One question, do you need 8N1 115200 bps imperiously for your application?. Is it not possible to change the baud rate of the devices you have to communicate with?.