Permalon liner is about $0.27/square foot. Its cross-laminated to give more strength in a thinner material. Its much less expensive than 40 mil polyethylene or EPDM. Will last much longer than vinyl or PVC. Permalon does not deal with rocks very well so if you have rocky soil you might want something thicker. Find it at:
www.reefindustries.com
Another poopular mid-range product is the fiber-reinforced polyethylene made by Unger. I cannot find a web site for them.
Before lining, you could have the contractor drag a sheep-foot roller over the pond to compact the soil and then a smooth roller to restore the surface.
I would just fertilize to get some biological activity going and give it some more time.
-steve hopkins