It's often found alongside natural gas because the rock structures that can trap methane can also trap other gasses, but the original source is different - thermal decomposition of organic matter for natural gas and radioactive decay, mostly of uranium and thorium, for helium.

I agree that the "accumulation over millions of years" is similar (and similarly a potential problem if we burn through all that accumulation).

Which is exactly 100% of Earth's helium. Every single helium atom we use is a result of alpha decay, as a very good approximation there isn't any primordial or stellar helium on or in Earth.