The ISP frequency can be up to 1/4 of the core clock so you must set you programmer to work at lower frequency. For 128KHz core clock the ISP can be up to 32KHz.
Use the -B flag of avrdude, try
-B250 ( 4kHz)
Specify the bit clock period for the JTAG interface or the ISP clock (JTAG ICE only). The value is a floating-point number in microseconds. The default value of the JTAG ICE results in about 1 microsecond bit clock period, suitable for target MCUs running at 4 MHz clock and above. Unlike certain parameters in the STK500, the JTAG ICE resets all its parameters to default values when the programming software signs off from the ICE, so for MCUs running at lower clock speeds, this parameter must be specified on the command-line. It can also be set in the configuration file by using the ’default_bitclock’ keyword.
If Arduiono ISP doesn't support that flag and you don't have any other programmer available you can use this
ArduinoISP firmware that supports low speed chip erase and fuse burning.