How energy of a photon or EM wave has something to do with frequency?

While I was thinking what exactly meant by energy in quantum mechanics, I was quite shocked by the fact that it is proportional to frequency.

$$E=hf$$

Given the fundamental definition of energy in classical mechanics is work done which is exactly energy transformed. (in newton mechanics, you get conservation of energy from this definition)

Now given Photoelectric effect, assuming light is indeed EM waves, now it seems to me indeed strange that electrons get more energy by a higher frequency. Since frequency has pretty much nothing to do with either "force" or "distance" in the fundamental definition above.

I wonder if this is how classical mechanics fails to predict Photoelectric effect? Is my reasoning correct? It seems something is missing in my reasoning, but I am not sure what it is.

Or perhaps, I should ask myself a counter question: how energy of a photon or EM wave has something to do with frequency?

---

Edited: Now I remember there is such a thing as Poynting vector. But I am still kind of confused, because Poynting vector is proportional to $\text{cos}^2(kr-wt)$, frequency's effect on energy density flux is bounded from zero to one. Perhaps I should ask another question about that.