The divots can be from sand washing some, but can also be from uneven settling; before replacing the liner, I'd back fill a small amount of lime and smooth- lime works well to completely fill the settled spots and redistrubute weight in house foundations, assume would work well here also.
another trick used in building is to fill with mortar mix- will compress in hollows, and will harden with time to prevent erosion some... not recommended for those not familiar with concrete and/or tile beds!
Good idea to use old pool liner as a protector for the new one!