A search for new phenomena giving rise to pairs of opposite electrically charged muons with impact parameters in the millimeter range is presented, using 139 fb⁻¹ of s=13 TeV pp collision data from the ATLAS detector at the LHC. The search targets the gap in coverage between existing searches targeting final states with leptons with large displacement and prompt leptons. No significant excess over the background expectation is observed and exclusion limits are set on the mass of long-lived scalar supersymmetric muon-partners (smuons) with much lower lifetimes than previously targeted by displaced muon searches. Smuon lifetimes down to 1 ps are excluded for a smuon mass of 100 GeV, and smuon masses up to 520 GeV are excluded for a proper lifetime of 10 ps, at 95% confidence level. Finally, model-independent limits are set on the contribution from new phenomena to the signal-region yields.