You might think that you'd need a large amount of water to make the energy release work, but I think it works like this. The force of the water on the air/water interface is dependent not on the reservoir volume, but on the weight of the water in the column (which depends only on the height of the shaft).
By digging a very deep shaft, you can have a very large force of water on the interface, and moving that interface an equal distance hence releases more energy than it would with a shorter shaft.
This way, you can store an arbitrary (up to your ability to compress air to a sufficient pressure, dig a deep shaft, and keep everything from blowing up) amount of energy.
I think if you have a 1 square meter cross section of shaft, and the shaft is 1 kilometer deep, then at the bottom the force of the water above is the weight of 1 square meter * 1 kilometer, or 1000 cubic meters of water, or 1 million kg.
The force then is 9.8×10^6 newtons.
Pressure is force/area, or 9.8×10^6 newtons/square meter here (since we have a unit area).
There's a formula for the energy in compressed air, it's... involved. I downloaded an excel file from here: https://ehs.berkeley.edu/publications/calculating-stored-ene...
It says under this pressure, a 1000 cubic meter tank of air at this pressure stores ~5000 KWh.
The one planned in California is supposed to store 4000 MWh, so I guess they have a tank that is ~a million cubic meters.
A water tank of the same size would store ~2700 MWh of energy (e.g., pumping that much water up a 1KM shaft requires that much energy), so it does seem to be more efficient.
It may also be that hot air turbines are cheaper and easier to maintain than hydropower turbines, but I'm not certain.