I have an algorithms recurrence $$T(m,n) = T(m/2,l) + T(m/2,n-l) + \mathcal{O}(mn)$$ where $0 \leq l \leq n$.
If $l = n/2$ is fixed, then it is quite easy to show that $T(m,n) = \mathcal{O}(mn)$.
However, in my problem, $l$ is not a constant, and it can vary throughout each recursive call. It turns out that $T(m,n) = \mathcal{O}(mn)$ even in this case, and the idea seems to be based on the fact that for the two sub-problems, $l + (n-l) = n$, but I am not sure how to turn this into a proof.
Based on comments I'm adjusting the answer. We have the recurrence:
$$ T(m, n) = T \left( \frac{m}{2}, l \right) + T \left( \frac{m}{2}, n - l \right) + k m n $$
where $l$ is some arbitrary value between $0$ and $n$, inclusive, and $k$ is a constant. We prove $T(m, n) = O(mn)$ using induction. We assume $T(m, n) \leq cmn$ for some constant $c$ and substitute into the recurrence and then apply induction:
$$ T(m, n) = T \left( \frac{m}{2}, l \right) + T \left( \frac{m}{2}, n - l \right) + k m n $$
$$ T(m, n) = c \frac{m}{2} l + c \frac{m}{2} (n - l) + k m n $$
$$ T(m, n) = c \frac{m}{2} n + k m n $$
$$ T(m, n) \leq c m n $$
which holds when $c \geq 2k$. And so we conclude $T(m, n) = O(mn)$ as you stated.