We constrain the rest-UV size-luminosity relation for star-forming galaxies at z~4 and z~6, 7, and 8 identified behind clusters from the Hubble Frontier Fields (HFF) program. The size-luminosity relation is key to deriving accurate luminosity functions (LF) for faint galaxies. Making use of the latest lensing models and full data set for these clusters, lensing-corrected sizes and luminosities are derived for 68 z~4, 184 z~6, 93 z ~7, and 53 z~8 galaxies. We show that size measurements can be reliably measured up to linear magnifications of ~30x, where the lensing models are well calibrated. The sizes we measure span a >1dex range, from <50pc to >~500pc. Uncertainties are based on both the formal fit errors and systematic differences between the public lensing models. These uncertainties range from ~10pc for the smallest sources to 100pc for the largest. Using a forward-modeling procedure to model the impact of incompleteness and magnification uncertainties, we characterize the size-luminosity relation at both z~4 and z~6-8. We find that the source sizes of star-forming galaxies at z~4 and z~6-8 scale with luminosity L as L^0.54+/-0.08^ and L_0.40+/-0.04^, respectively, such that lower-luminosity (>~-18mag) galaxies are smaller than expected from extrapolating the size-luminosity relation at high luminosities (<~-18mag). The new evidence for a steeper size-luminosity relation (3{sigma}) adds to earlier evidence for small sizes based on the prevalence of highly magnified galaxies in high-shear regions, theoretical arguments against upturns in the LFs, and other independent determinations of the size-luminosity relation from the HFF clusters.