As far as I know, all forms of algae can be brushed off. And, metal stains would get worse, not better, when you shock.

Could it be fungus bleed-through? That's the only thing I can think of that would behave the way you describe.

If the ground is damp on the non-pool side of the liner, dark fungal or bacterial colonies will sometimes form next to the liner. The pigment from these will penetrate the liner, and show up on the POOL side of the liner. Very high chlorine levels will bleach out the organic pigment, but only on the surface of the liner. The only solution is to (a) dry out the ground under the liner or (b) treat the area with high levels of an persistent anti-fungal, like a mixture of borax and copper sulfate.

I won't ask you to photograph it since when I've seen it, it was never something you could photograph, unless you have underwater gear and high quality off-camera underwater lighting or flash. But, you might swim down with goggles and take a look -- it has roughly the same color as fungal staining on an old white towel.

Let me know what you find.