We investigate the decoherence of $^{40}$K impurities interacting with a three-dimensional Fermi sea of $^{6}$Li across an interspecies Feshbach resonance. The decoherence is measured as a function of the interaction strength and temperature using a spin-echo atom interferometry method. For weak to moderate interaction strengths, we interpret our measurements in terms of scattering of K quasiparticles by the Fermi sea and find very good agreement with a Fermi liquid calculation. For strong interactions, we observe significant enhancement of the decoherence rate, which is largely independent of temperature, pointing to behavior that is beyond the Fermi liquid picture.