AWS is notorious for being extremely expensive, so it's not like they became cheap. They just reduce prices from extremely expensive to slightly less extremely expensive, and that makes more people decide to start using it.

Since the price they are charging is still way, way above their operating costs there's no surprise really that they end up making more from small price reductions.

If competition drove them to reduce costs to the point where their operating costs started to be a large factor, the paradox would disappear.