I think the first step is to check if the liner will even come clean.

Try scrubbing a section a foot or so down and see if the crud comes off.

If it does, then it might be worth trying to clear the water and see if you can brush the liner clean. A smaller investment before you commit to liner replacement.