Hall effect and quantum oscillation measurements on high temperature cuprate superconductors show that underdoped compositions have small Fermi surface pockets whereas when heavily overdoped, a single much larger pocket is found. The origin of this change in electronic structure has been unclear, but may be related to the high temperature superconductivity. Here we show that the clean overdoped single-layer cuprate Tl2Ba2CuO6+δ (Tl2201) displays CDW order with a remarkably long correlation length ξ ≈ 200 Å which disappears above a hole doping of pCDW ≈ 0.265. We show that the evolution of the electronic properties of Tl2201 as the doping is lowered may be explained by a Fermi surface reconstruction which accompanies the emergence of the CDW below pCDW. Our results demonstrate importance of CDW correlations in understanding the electronic properties of overdoped cuprates.