It is not true that the increase in von Neumann entropy of entanglement between the two partitions due to a single cross-partition two-qubit gate is at most one. See below for an example where the increase is two. However, we can use log Schmidt rank to justify a different asymptotically linear upper bound.
Product states
A two-qubit gate cannot produce more than one ebit of entanglement when applied to a product state. This follows from Schmidt decomposition and the fact that the Hilbert space of one qubit is two-dimensional.
Counterexample
However, the argument fails when the qubits to which the gate is applied have preexisting entanglement with other qubits. For example, consider four qubits $A_1A_2B_1B_2$ in the state
$$
|\psi_0\rangle = \frac12(|0_{A_1}0_{A_2}\rangle+|1_{A_1}1_{A_2}\rangle)\otimes(|0_{B_1}0_{B_2}\rangle+|1_{B_1}1_{B_2}\rangle).\tag1
$$
Clearly, the initial entanglement entropy between the partition $A=A_1A_2$ and $B=B_1B_2$ is zero. However, following a single SWAP gate applied to qubits $A_2$ and $B_1$, we get
$$
|\psi_1\rangle = \frac12(|0_{A_1}0_{B_1}\rangle+|1_{A_1}1_{B_1}\rangle)\otimes(|0_{A_2}0_{B_2}\rangle+|1_{A_2}1_{B_2}\rangle)\tag2
$$
with the reduced state of partition $A$
$$
\rho=\mathrm{tr}_{B}(|\psi_1\rangle\langle\psi_1|)=\frac{I_2}{2}\otimes\frac{I_2}{2}=\frac{I_4}{4}\tag3
$$
and entanglement entropy $S(\rho)=2$.
Schmidt rank
By Schmidt decomposition, a state $|\phi\rangle$ of partitions $A$ and $B$ can be written as
$$
|\phi\rangle = \sum_{i=1}^m\lambda_i|i_A\rangle|i_B\rangle\tag4
$$
where $\lambda_i>0$ are Schmidt coefficients and $|i_X\rangle$ are orthonormal states of partition $X=A,B$. The number $m$, often denoted by $\mathrm{Sch}(|\phi\rangle)$ and called the Schmidt rank of the bipartite state $|\phi\rangle$, is another important measure of entanglement.
For any $m$ positive real numbers $s_1, \dots, s_m$ summing to $1$, the Shannon entropy $H(s_1,\dots,s_m)\le\log m$. Therefore, the logarithm of the Schmidt rank provides an upper bound on von Neumann entropy
$$
S(\mathrm{tr}_B(|\psi\rangle\langle\psi|)) \le \log\mathrm{Sch}(|\psi\rangle)\tag5
$$
for any pure bipartite state $|\psi\rangle$.
Increase in log Schmidt rank due to one gate
We can derive an upper bound on the increase in log Schmidt rank due to a single two-qubit cross-partition gate. Suppose the gate $U$ has operator Schmidt rank $r$, i.e. can be written as
$$
U=\sum_{j=1}^rR_j\otimes S_j\tag6
$$
for some single-qubit operators $R_j$ and $S_j$ acting on a qubit in partition $A$ and $B$, respectively and orthogonal with respect to Hilbert-Schmidt inner product (see e.g. $6.4.2$ in Nielsen's PhD thesis or this paper for more details on operator variant of Schmidt decomposition). Then $U|\phi\rangle$ may be written as
$$
\begin{align}
|\phi'\rangle=U|\phi\rangle&=\sum_{i=1}^m\sum_{j=1}^r\lambda_iR_j|i\rangle S_j|i'\rangle \\
&= \sum_{k=1}^{mr}\mu_k|k''\rangle|k'''\rangle
\end{align}\tag7
$$
so$^1$ $|\phi'\rangle$ has Schmidt rank at most $mr$.
Now, $R_j$ and $S_j$ belong to the complex vector space of operators on $\mathbb{C}^2$ which is four dimensional. Therefore, for a two-qubit gate $r\le 4$. We conclude that a two qubit gate can increase the log Schmidt rank by at most two.
Linear bound on von Neumann entropy
Therefore, by $(5)$ the final von Neumann entropy $S_f$ of entanglement between the two partitions after running a circuit with $Md$ cross-partition two-qubit gates can be bounded above as
$$
S_f\le 2Md.\tag8
$$
Even though $(8)$ is not as tight as $Md$, it is still asymptotically linear.
$^1$ Every representation of a bipartite state $|\psi\rangle$ as a sum of product states has at least $\mathrm{Sch}(|\psi\rangle)$ terms. See e.g. Problem $2.2$ on page $117$ in Nielsen & Chuang.
