The following is a self-answered question; I think the question posed here is natural, and I also need this to be stated as a separate result, for a more advanced question to come.
Alternative solutions are welcome.
Let $M$ be a complete Riemannian manifold.
Let $p,q \in M$. Then for any $\epsilon >0$ there exist a $\delta >0$ such that, if $\alpha$ is a path between $p,q$ such that $L(\alpha) < d(p,q) + \delta$ then $\alpha$ is in an $\epsilon$-neighbourhood of some minimizing geodesic $\gamma$ joining $p,q$. That is, there exists a reparametrization $\alpha \circ \varphi:I \to M$ and a minimizing geodesic $\gamma:I \to M$ joining $p,q$ such that $\forall t \, \,d\big((\alpha \circ \varphi)(t),\gamma(t)\big) < \epsilon$.
Assume by contradiction the claim is false.
Then there exists an $\epsilon > 0$, and a sequence of paths $\alpha_n:I \to M$ joining $p,q$ such that, $L(\alpha_n) \le d(p,q) + \frac{1}{n}$, and $\alpha_n$ is not in an $\epsilon$ neighbourhood of any minimizing geodesic.
Since $L(\alpha_n)\to d(p,q)=r$, we can assume $\operatorname{Image}(\alpha_n) \subseteq \bar B^M(p,2r)$ (the closed ball of radius $2r$ around $p$). By completeness of $M$ , $\bar B^M(p,2r)$ is compact.
We can reparametrize $\alpha_n$ by arclength, thus assuming they are equicontinuous. By Arzela-Ascoli, there exists a subsequence $\alpha_n$ which converges uniformly to $\alpha:I \to M$.
By lower semicontinuity of the length functional, $L(\alpha) \le \lim_{n \to \infty} L(\alpha_n) = d(p,q) $.
This implies $\alpha$ is length minimizing in $M$, hence there exists a reparametrization $\alpha \circ \varphi$ which is a geodesic.
The convergence $\alpha_n \to \alpha$ gives us a contradiction: $d\big((\alpha_n \circ \varphi)(t),(\alpha \circ \varphi)(t)\big) < \epsilon$ for sufficiently large $n$.