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$\mathrm{<mrow\; data-mjx-texclass="ORD">-1</mrow>}$, 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.