The reason is that your statement is true only for sine waves. In logic circuits there is a small current spike everytime a gate switches from a logic 1 to a logic 0 and vice versa. This is very short in duration (nanoseconds or less). The amount of energy consumed during this spike is pretty much constant. As you increase clock frequency you get more spikes every second. As power is energy per unit time you can see the power goes up with frequency. This is known as the 'speed power product'. Check it out on Google if you want intimate details.

Ian