We had the same problem, two years in a row we lost almost half the water over the winter. Looked for the leak all last summer with no luck. There is lots of good info on here for finding leaks but none of it worked for me. This years i said screw it and decided to just replace to liner, first to fix the leak and second to see where it was. To my surprise the leak i have been searching for was not one, but many small, very small ones all around the cove, i would have never found them i had not gone under the liner after i emptied the pool. I was convinced my leak was within inches of the water line in in fact it was no where near it.

I think the tell tale sign of one many small leaks vs a few larger ones is the fact that my pool look like it was loosing water, then the next week it would seem to loose none or very little. I think this was caused by my many small leaks getting plugged up by debris and sand, then after a good day of swimming, the water would get mixed up and the holes would open. If i had had larger leaks, i bet my water loss would have been more steady.