Efficiently selecting a random subset of size $m$ from a set of size $n$
The probability that the element $1$ belongs to a random $m$-subset of an $n$-element set is $m/n$. Therefore you should include $1$ in your subset with probability $m/n$.
If you put $1$ in your subset, then you are left with choosing an $(m-1)$-subset of an $(n-1)$-element set.
If you didn't put $1$ in your subset, then you are left with choosing an $m$-subset of an $(n-1)$-element set.
This means that you have to slightly update your algorithm, replacing $m$ with $m-|L|$.
The resulting algorithm is somewhat similar to reservoir sampling.
A third approach, with some similarities, is generating a random permutation of $1,\ldots,n$ and selecting the first $m$ entries.
The downside of all of these approaches are that they run in time $\Theta(n)$, whereas for $m \ll \sqrt{n}$, your first algorithm runs in (expected) time $\tilde\Theta(m)$.
We can improve on the $\Theta(n)$ running time as follows. We will generate a random ordered $m$-subset given $m$ indices $i_1,\ldots,i_m$, where $i_j \in \{1,\ldots,n-(j-1)\}$. The $j$'th element in the subset will be the $i_j$'th smallest number in $\{1,\ldots,n\}$ out of the numbers not already chosen.
In order to complete the description of the algorithm, we need to solve the following problem: given $S \subseteq \{1,\ldots,n\}$ and $i$, find the $i$'th smallest element in $\overline{S}$. We can assume that $S$ is stored in a structure (such as a self-balancing binary tree) which can efficiently answer the following type of query: given $x$, how many elements in $S$ are smaller than $x$. We can then find the $i$'th smallest number in $\overline{S}$ using binary search.
Overall, this algorithm runs in $\tilde\Theta(m)$ for all values of $m$, where the tilde hides factors logarithmic in $n$. (When $m \ll \sqrt{n}$ we can use your first approach, thus getting rid of this dependence on $n$.)