I was able to figure this out by viewing $M$ as a scaled Cauchy matrix.

**Theorem.** $\left(M^{-1}\right)_{ij} = \dfrac{(n-i)!(n-j)!}{2n-i-j+1}\dfrac{\displaystyle\prod_{r=1}^{n}(2n-i-r+1)(2n-j-r+1)}{\left(\displaystyle\prod_{\stackrel{r=1}{r\neq i}}^{n}(r-i)\right) \left(\displaystyle\prod_{\stackrel{r=1}{r\neq j}}^{n}(r-j)\right)}$.

**Proof.** Define $n\times 1$ vector $\alpha$ with elements $(\alpha)_{i} = 1/(n-i)!$. Then $M = \text{diag}(\alpha) N \text{diag}(\alpha)$, where $N_{ij} := 1/(2n-i-j+1)$. Hence $\left(M^{-1}\right)_{ij} = (n-i)!(n-j)!\left(N^{-1}\right)_{ij}$.

Now, write $N$ as a Cauchy matrix: $N_{ij} = 1/(a_i + b_j)$ where $a_i := n-i$, $b_j := n-j+1$. Then using the known result [1, Sec. 1.2.3, Exercise 41] for Cauchy matrix inverse:
$$\left(N^{-1}\right)_{ij} = \dfrac{1}{2n-i-j+1}\dfrac{\displaystyle\prod_{r=1}^{n}(2n-i-r+1)(2n-j-r+1)}{\left(\displaystyle\prod_{\stackrel{r=1}{r\neq i}}^{n}(r-i)\right) \left(\displaystyle\prod_{\stackrel{r=1}{r\neq j}}^{n}(r-j)\right)},$$
the result follows.

[1] D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, 3rd ed. Addison- Wesley, 1997.