Here is a sketch: Please check and tell me if you want more or corrections.
Answer
Using the usual notation $\tilde{M}(1,2)\cong M(a+1,b+2)$
$\tilde{M}(1,2)=\frac{(2\cdot b^{2}+2\cdot b)\cdot z^{2}+(-b^{4}+(2\cdot a-2)\cdot b^{3}+3\cdot b^{2}+(4-2\cdot a)\cdot b)\cdot z+b^{5}-2\cdot b^{4}-b^{3}+2\cdot b^{2}}{(a\cdot b^{2}+(-a^{2}-2\cdot a)\cdot b+2\cdot a^{2})\cdot z^{2}}\tilde{M}(0,0)+\frac{(2\cdot b^{3}-2\cdot b)\cdot z-b^{5}+(a+1)\cdot b^{4}+b^{3}+(-a-1)\cdot b^{2}}{(a\cdot b^{2}+(a-2\cdot a^{2})\cdot b+a^{3}-a^{2})\cdot z^{2}}\tilde{M}(-1,-2)$
First we define two new sequences:
Starting at n=0
$(n,n+1,n+2,n+3)\rightarrow\left(m,l,m+1,l+1\right)$
n even
$m=\frac{n}{2},M\left(m,2\cdot m+\frac{3}{2};-z\right)\rightarrow M\left(m+1,2\cdot m+\frac{3}{2}+2;-z\right)$
n odd
$l=\frac{n+1}{2} ,M\left(l,2\cdot l+\frac{3}{2};-z\right)\rightarrow M\left(l+1,2\cdot l+\frac{3}{2}+2;-z\right)$
Rearranging DLMF 13.3.2 we can bump $b\rightarrow b+2$
$M(a,b+2;-z)=\frac{\left(b-1\right)\cdot\left(b+z\right)}{z\cdot\left(b+1-a\right)}M\left(a,b+1;-z\right)+\frac{b\cdot\left(b+1\right)}{z\cdot\left(b+1-a\right)}M\left(a,b;-z\right)$
And subsequently 13.3.3 $a\rightarrow a+1$
$M\left(a+1,b+2;-z\right)=\frac{\left(a-\left(b+2\right)+1\right)}{a}M\left(a,b+2;-z\right)+\frac{\left(b+1\right)}{z}M\left(a,b+1;-z\right)$
Where I haven't reduced expressions in order to make tracking DLMF easier
Using obvious substitutions to get j,k ;we have the single recursion
$M\left(a+1,b+2;-z\right)=k\cdot M\left(a,b+1;-z\right)+j\cdot M\left(a,b;-z\right)$
I will fill in j,k if needed.
This can be applied to both n even (m) or odd (l) as above.
The calculation of the real requested recursion follows.
Alternate ways to find a recursion
I recomend skipping to "Obvious solution" ; I left the "Simple Matrix algebra" for the record. It does use some higher power tools (and less programming) but is less obvious.
$r\cdot M\left(a,b,z\right)+s\cdot M(a+1,b+2,z)=M(a+2,b+4)$
Simple Matrix algebra
With a modicum of identity selection we can select from the contiguous relations, like so:
Make a matrix expression.
$$\left[\begin{array}{ccccc}
r & s & t & u & v\end{array}\right]\begin{pmatrix}\mathit{a1} & \mathit{a2} & \mathit{a3} & 0 & 0 & 0 & 0\\
0 & \mathit{b2} & 0 & 0 & \mathit{b5} & \mathit{b6} & 0\\
0 & 0 & \mathit{c3} & \mathit{c4} & 0 & 0 & \mathit{c7}\\
\mathit{d1} & 0 & 0 & 0 & 0 & \mathit{d6} & \mathit{d7}\\
0 & 0 & 0 & \mathit{e4} & 0 & \mathit{e6} & \mathit{e7}
\end{pmatrix}\left[\begin{array}{c}
\tilde{M}(0,0)\\
\tilde{M}\left(1,1\right)\\
\tilde{M}\left(-1,-1\right)\\
\tilde{M}\left(-1,-2\right)\\
\tilde{M}\left(1,2\right)\\
\tilde{M}\left(1,0\right)\\
\tilde{M}\left(0,-1\right)
\end{array}\right]
$$
$$r,s,t,u,v$$ are the weights to combine rows/identities for required output.
The rows correspond to DLMF
13.3.13 (a,b offset by -1,-1)
$M(a,b,z)\cdot b\cdot(-z+b-1)+a\cdot z\cdot M(a+1,b+1,z)-M(a-1,b-1,z)\cdot(b-1)\cdot b$
13.3.2 (a,b offset by 1,1)
$M(a+1,b+1,z)\cdot(b+1)\cdot(-z-b)-M(a+1,b+2,z)\cdot(b-a)\cdot z+M(a+1,b,z)\cdot b\cdot(b+1)$
13.3.3 (a,b offset by -1,-1)
$M(a-1,b-1,z)\cdot(-b+a+1)+M(a-1,b-2,z)\cdot(b-2)-(a-1)\cdot M(a,b-1,z)$
13.3.3
$M(a,b,z)\cdot(-b+a+1)-a\cdot M(a+1,b,z)+M(a,b-1,z)\cdot(b-1)$
13.3.13 ( a,b offset by -1,-2)
$-M(a-1,b-2,z)\cdot\left(b-2\right)\cdot(b-1)+a\cdot z\cdot M(a+1,b,z)+M(a,b-1,z)\cdot\left(b-1\right)\cdot(-z+b-2)$
Substituting the identity coefficients we get:
$\begin{pmatrix}\mathit{b\cdot(-z+b-1)} & a\cdot z & \mathit{-b\cdot\left(b-1\right)} & 0 & 0 & 0 & 0\\
0 & \mathit{\left(b+1\right)\cdot\left(-b-z\right)} & 0 & 0 & -z\cdot\left(b-a\right) & \mathit{b\cdot\left(b+1\right)} & 0\\
0 & 0 & \mathit{\left(a-b-1\right)} & \mathit{\left(b-2\right)} & 0 & 0 & \mathit{-\left(a-1\right)}\\
\mathit{\left(a-b-1\right)} & 0 & 0 & 0 & 0 & \mathit{-a} & \mathit{\left(b-1\right)}\\
0 & 0 & 0 & \mathit{-\left(b-2\right)\cdot\left(b-1\right)} & 0 & \mathit{z\cdot a} & \mathit{\left(b-1\right)\cdot\left(b-z-2\right)}
\end{pmatrix}$
We can work against either representation. I cheated a little and used elim() in Maxima computer algebra to eliminate $[a2,a3,b6,b7]$ to compute $[r,s,t,u,v]$ . The correct columns went to zero as indicated by the multiplication $saam\,.\,aa$ below. I really should make a cleaner explanation for this choice.
Weights (r is left free)
$$saam=
\begin{pmatrix}r & -\frac{\mathit{a2} r}{\mathit{b2}} & -\frac{\mathit{a3} r}{\mathit{c3}} & \frac{\left( \mathit{a2}\, \mathit{b6}\, \mathit{c3}\, \mathit{e7}-\mathit{a3}\, \mathit{b2}\, \mathit{c7}\, \mathit{e6}\right) r}{\mathit{b2}\, \mathit{c3}\, \mathit{d6}\, \mathit{e7}-\mathit{b2}\, \mathit{c3}\, \mathit{d7}\, \mathit{e6}} & -\frac{\left( \mathit{a2}\, \mathit{b6}\, \mathit{c3}\, \mathit{d7}-\mathit{a3}\, \mathit{b2}\, \mathit{c7}\, \mathit{d6}\right) r}{\mathit{b2}\, \mathit{c3}\, \mathit{d6}\, \mathit{e7}-\mathit{b2}\, \mathit{c3}\, \mathit{d7}\, \mathit{e6}}\end{pmatrix}$$
Substituting for the $a_{m},b_{n},c_{o},d_{p},e_{q}$ we have
$saam2=$
$\begin{array}{ccc}
[r, & \frac{arz}{(b+1)z+b^{2}+b} & ,-\frac{\left(b^{2}-b\right)\cdot r}{b-a+1},-\frac{b^{2}\cdot r\cdot z^{2}+(-b^{3}+2a\cdot b^{2}+(2-2a)b)r\cdot z}{(b^{2}+(-a-1)\cdot b+2a-2)\cdot z+b^{3}+(-a-1)\cdot b^{2}+(2a-2)\cdot b},\,\frac{b^{2}\cdot r\cdot z+(a-1)\cdot b^{2}\cdot r}{(b^{2}+(-a-1)\cdot b+2\cdot a-2)\cdot z+b^{3}+(-a-1)\cdot b^{2}+(2\cdot a-2)\cdot b}]\end{array}$
Result of matrix multiplication
$saam\,.\,aa $
$[\frac{(2\cdot b\cdot r\cdot z^{2}+(-b^{3}+(2\cdot a-1)\cdot b^{2}+(4-2\cdot a)\cdot b)\cdot r\cdot z+(b^{4}-3\cdot b^{3}+2\cdot b^{2})\cdot r)}{((b-2)\cdot z+b^{2}-2\cdot b)},0,0,\frac{(2\cdot b^{2}-2\cdot b)\cdot r\cdot z+(-b^{4}+(a+2)\cdot b^{3}+(-a-1)\cdot b^{2})\cdot r}{(b-a+1)\cdot z+b^{2}+(1-a)\cdot b},\frac{(a\cdot b-a^{2})\cdot r\cdot z^{2}}{(b+1)\cdot z+b^{2}+b},0,0]$
Using the substitution we have
$\tilde{M}(1,2)=\frac{(2\cdot b^{2}+2\cdot b)\cdot z^{2}+(-b^{4}+(2\cdot a-2)\cdot b^{3}+3\cdot b^{2}+(4-2\cdot a)\cdot b)\cdot z+b^{5}-2\cdot b^{4}-b^{3}+2\cdot b^{2}}{(a\cdot b^{2}+(-a^{2}-2\cdot a)\cdot b+2\cdot a^{2})\cdot z^{2}}\tilde{M}(0,0)+\frac{(2\cdot b^{3}-2\cdot b)\cdot z-b^{5}+(a+1)\cdot b^{4}+b^{3}+(-a-1)\cdot b^{2}}{(a\cdot b^{2}+(a-2\cdot a^{2})\cdot b+a^{3}-a^{2})\cdot z^{2}}\tilde{M}(-1,-2)$
Where the third term is the coefficient of $M(1,2)$ and the first term is the coefficient of $M(0,0)$ and the fourth term is the coefficient of $M(-1,-2)$.
“Obvious solution”
Rather than belabor the details I will just generally show the principle; which is simply a form of Gaussian Elimination/Back Substitution.
Consider 5 independent constraints/identities applied to 7 functions M1, M2, M3, M5, M6, M7.
$$ \begin{pmatrix}\mathit{M6}\,\mathit{a6}+\mathit{M4}\,\mathit{a4}+\mathit{M1}\,\mathit{a1}\\
\mathit{M5}\,\mathit{b5}+\mathit{M4}\,\mathit{b4}+\mathit{M2}\,\mathit{b2}\\
\mathit{M7}\,\mathit{c7}+\mathit{M5}\,\mathit{c5}+\mathit{M3}\,\mathit{c3}\\
\mathit{M7}\,\mathit{d7}+\mathit{M6}\,\mathit{d6}+\mathit{M2}\,\mathit{d2}\\
\mathit{M7}\,\mathit{e7}+\mathit{M6}\,\mathit{e6}+\mathit{M3}\,\mathit{e3}
\end{pmatrix}=\left(\begin{array}{c}
0\\
0\\
0\\
0\\
0
\end{array}\right)
$$
We represent this as $A\left(5,7\right)$ and our goal will be $A\left(1,3\right)$, that is the trilinear $f(M1,M2,M3)$.
But this is obvious: for instance we start from the bottom and solve for M7 and substitute back into the equations. We now have 4 equations in 6 unknowns: i.e.
$A(5,7)\rightarrow A(4,6)$
and so on for M6, M5, M4 and having eliminated everything but M1, M2, M3 we have our answer. This is three lines of Maxima code.
The only obstruction is if a back substitution leaves an additional zero constraint. In this case the constraints/identities were redundant and one of the constraints is a linear combination the others and you have to find a new constraint or settle for having another $MX$ in your result.
The Independence can also be calculated beforehand by exterior calculus or in matrix minors terms.
Exterior Calculus
I am leaving this out because I am not satisfied with my explanations. The factoring of linear dependence in the language of the “/\” operations seems intuitively obvious but a little complicated to put into words (and it shouldn't be). In addition I am not satisfied that it really adds to the previous process; i.e. it's just a rehash.