A search for new physics with non-resonant signals in dielectron and dimuon final states in the mass range above 2 TeV is presented. This is the first search for non-resonant signals in dilepton final states at the LHC to use a background estimate from the data. The data, corresponding to an integrated luminosity of 139 fb, were recorded by the ATLAS experiment in proton-proton collisions at a center-of-mass energy of s = 13 TeV during Run 2 of the Large Hadron Collider. The benchmark signal signature is a two-quark and two-lepton contact interaction, which would enhance the dilepton event rate at the TeV mass scale. To model the contribution from background processes a functional form is fit to the dilepton invariant-mass spectra in data in a mass region below the region of interest. It is then extrapolated to a high-mass signal region to obtain the expected background there. No significant deviation from the expected background is observed in the data. Upper limits at 95% CL on the number of events and the visible cross-section times branching fraction for processes involving new physics are provided. Observed (expected) 95% CL lower limits on the contact interaction energy scale reach 35.8 (37.6) TeV. [Figure not available: see fulltext.]