Lead-halide perovskites have attracted tremendous attention, initially for their performance in thin film photovoltaics, and more recently for a variety of remarkable optical properties. Defect tolerance through polaron formation within the ionic lattice is a key aspect of these materials. Polaron formation arises from the dynamical coupling of atomic fluctuations to electronic states. Measuring the properties of these fluctuations is therefore essential in light of potential optoelectronic applications. Here we apply two-dimensional electronic spectroscopy (2DES) to probe the timescale and amplitude of the electronic gap correlations in CsPbI3 perovskite nanocrystals via homogeneous lineshape dynamics. The 2DES data reveal irreversible, diffusive dynamics that are qualitatively inconsistent with the coherent dynamics in covalent solids such as CdSe quantum dots. In contrast, these dynamics are consistent with liquid-like structural dynamics on the 100 femtosecond timescale. These dynamics are assigned to the optical signature of polaron formation, the conceptual solid-state analogue of solvation.