Reducing Clock Speed increases sketch size?
Does your code have delays in it? If you changed the clock speed, then the compiled assembly for the delays may require more NOP instructions or something similar to achieve the same real-time delay. As a result, the size of the compiled sketch could increase.