By induction, it is immediate that $a_{m,n}\le 2\min(m,n)$. In addition, when $m$ is fixed and $n>m$ we have $a_{m,n}=2m-P_m(n)/2^n$, where $P_m(x)$ is a polynomial of degree $m$, so $2m$ is an exponentially good bound. For $m=n$, it would be interesting to investigate if $a_{n,n}/n$ tends to $2$ and if yes, at what speed.