Why is this charge-pump regulator less efficient when operating with a lower supply voltage?
It's a charge-pump DC to DC converter and when, theroretically, the input voltage is 2.5V it can charge "the" capacitor up to 2.5V then electrically reposition it to add 2.5V to the input voltage to produce an output voltage of 5V. 

This is always going to be its most efficient setup because, if your input supply is (say) 3V and you charged the capacitor fully the output would normally become 6V so, 1V has to be lost (in order to produce a 5V output). This loss is created by not fully charging the capacitor up to the incoming supply voltage in the first place. 

Now, with any charge pump voltage generator the losses (inefficiences) occur when charging the capacitor. The lack of an inductor means that these losses are due to internal charging resistors and this is real power dissipation unlike a conventional buck or boost converter. 

The biggest loss occurs when initially charging the capacitor - this loss falls as the capacitor charges closer to the incoming supply voltage. This is because the charge current naturally reduces and the resistor \$I^2R\$ power loss falls away.

So, bigger inefficiences occur when the input voltage is slightly less than the required output voltage. Let's say the required output is 5V and the input voltage is 4.9 volts - the capacitor has to be charged to 0.1 volts so it can add (caused by the internal H bridge repositioning it electrically) to the incoming supply to produce 5V at the output. Thus It spends all of its charging time at the most power hungry part of the charge cycle.