The impact of nuclear deformation can been seen in the systematics of nuclear charge radii, with radii generally expanding with increasing deformation. In this Letter, we present a detailed analysis of the precise relationship between nuclear quadrupole deformation and the nuclear size. Our approach combines the first measurements of the changes in the mean-square charge radii of well-deformed palladium isotopes between A=98 and A=118 with nuclear density functional calculations using Fayans functionals, specifically Fy(std) and Fy(Δr,HFB), and the UNEDF2 functional. The changes in mean-square charge radii are extracted from collinear laser spectroscopy measurements on the 4d^{9}5s ^{3}D_{3}→4d^{9}5p ^{3}P_{2} atomic transition. The analysis of the Fayans functional calculations reveals a clear link between a good reproduction of the charge radii for the neutron-rich Pd isotopes and the overestimated odd-even staggering: Both aspects can be attributed to the strength of the pairing correlations in the particular functional which we employ.