if both ATmega8 and ATmega168 support 20Mhz
They don't - the original Arduino was based on the ATmega8, which has a max frequency of 16MHz.
Wouldn't be any issues with Software Serial or anything else with this increase in speed?
QuoteWouldn't be any issues with Software Serial or anything else with this increase in speed?Yes. UART timing, delay(), delayMilliseconds() and millis() timing, as well as the bootloader I mentioned before.
The bootloader is the showstopper, as it requires a hardware programmer to change it.
There's a 20MHz bootloader out there, and programmers of varying cost. If you really need 20MHz it's within reach.