Complexation between anionic and cationic polyelectrolytes results in solid-like precipitates or liquid-like coacervate depending on the added salt in the aqueous medium. However, the boundary between these polymer-rich phases is quite broad and the associated changes in the polymer relaxation in the complexes across the transition regime are poorly understood. In this work, the relaxation dynamics of complexes across this transition is probed over a wide timescale by measuring viscoelastic spectra and zero-shear viscosities at varying temperatures and salt concentrations for two different salt types. We find that the complexes exhibit time-temperature superposition (TTS) at all salt concentrations, while the range of overlapped-frequencies for time-temperature-salt superposition (TTSS) strongly depends on the salt concentration (C_s) and gradually shifts to higher frequencies as C_s is decreased. The sticky-Rouse model describes the relaxation behavior at all C_s. However, collective relaxation of polyelectrolyte complexes gradually approaches a rubbery regime and eventually exhibits a gel-like response as C_s is decreased and limits the validity of TTSS.