According to Adafruit's pdf specsheet SIM800+Series_Serial+Port_Application+Note_V1.01.pdf, the SIM800 is set up to auto-baud when it starts out:
SIM800 series is designed in autobauding mode by default. Autobauding allows SIM800 series to automatically detect the baud rate of the host device. In application, host device must to synchronize the baud rate with SIM800 series. Host device must firstly send characters "AT" or "at" to synchronize the baud rate. It is recommended to send "AT" until host device receives the "OK" response, which means host device and SIM800 series are correctly synchronized. Once the baud rate is synchronized, it is suggested to use AT command "AT+IPR" to set SIM800 series baud rate according the host baud rate. ...
So, you might arrange your software to keep trying at 9600 bps. If you get an ok connection at that rate, you can either keep using it or shift to a higher frequency via "AT+IPR". [I haven't read the spec sheet enough to know whether that default autobauding is always on, or might be turned off somehow.]
As serial-data bps goes up, required clock accuracy becomes tighter. Where a couple of percent error may be ok at 9600 bps, under a percent probably is needed at 115200 bps.
On several boards I've measured RC oscillator frequency errors of about 2%, which according to question How critical are UART frequencies? might or might not be good enough to allow high-speed serial communications.
If you can measure your ATmega328P's RC oscillator frequency, you can then apply a correction factor at startup. In the spec sheet (eg Atmel-8271J-AVR-ATmega-Datasheet_11/2015), see §9.12.1, OSCCAL – Oscillator Calibration Register.
Your program can start out with the RC oscillator using the factory-set value, and then can load your own calibration value into the Oscillator Calibration Register to shift RC frequency as needed to make the board work ok for 115200 bps serial data. Or, you can overwrite (in EEPROM fuse or signature area) the factory-set value with your own number.
Figure 32-37, ATmega48PA: Calibrated 8MHz RC Oscillator Frequency vs. OSCCAL Value, shows typical frequencies for various Oscillator Calibration Register values. It is possible to tune clock frequency close enough that serial communications should work ok.
High-range byte values 144 through 160 typically move frequency from around 7.4 MHz to 8 MHz (at 85℃). In this range, each count shifts clock frequency by about 0.5%. See the figure for details. For example, if value 158 gives an RC frequency of about 7820 KHz, then value 159 might raise the RC frequency to about 7860 KHz.
Low-range entries 96 through 112 move frequency from around 7.5 MHz to 8.5 MHz. This overlap makes it necessary to try both low-range and high-range values when looking for the best Calibration Register value.
Note, there are inexpensive cymometers (frequency counters) on ebay, which can measure oscillator frequencies accurately enough to enable the calibration suggested above.