Star formation timescales are key to understanding fundamental physics like feedback mechanisms, as well as the abundance of bright galaxies at z>10. We investigate galaxy star formation histories (SFHs) and their evolution across z~3–9 by measuring the line-to-UV ratio (Rline) and line equivalent width (EW) of Hα+[N II] and [O III]+Hβ directly from UNCOVER/MegaScience spectro-photometry without relying on a specific SFH or nebular line modeling. Our photometric measurements recover Rline and EW to <10 systematic accuracy compared to spectroscopy. This allows us to construct a large mass- (and flux-) complete sample and quantitatively examine how Rline evolves with redshift and stellar mass. We find that the intrinsic scatter in Rline does not significantly evolve with redshift across 3<z<7, though it may increase at z ≳ 8. We build population-level toy models using Rline to help interpret our observations, and find that scatter in Rline primarily reflects the amplitude of SFH fluctuations; this implies that our observed lack of evolution in the scatter of Rline is due to similar star formation burstiness from z~3 to z~7. Our observations are best reproduced by a set of SFHs with rising, long-duration, and large-amplitude bursts. Finally, we demonstrate that the toy model that best describes our z~6 data can boost UV brightness by up to ∆MUV~-2.0mag compared with a 200Myr constant SFH, and naturally produces a large number of galaxies at z>10. This suggests that no significant evolution in star formation burstiness is required to explain the abundance of UV-bright galaxies at high redshift.