$A_N$ has order of magnitude $N^3$:
We use the change of variables $x=k-m$, $y=k+m$, $u=n-l$, $v=n+l$. If $x=0$ or $u=0$, there are clearly $\ll N^3$ solutions.
Given $x\ge u \ge 1$ and $y$, the 
variable $v$ must satisfy
$$
v \in [2N-u,2N+u] \cap \left[ \frac{xy}{u}-\frac{x-u}{u},  \frac{xy}{u}\right].
$$
For this intersection to be non-empty, we must have $x/u \asymp 1$, since $y \asymp N$. This implies that the width of the second interval is $O(1)$. 
Thus there are $O(1)$ choices for $v$, which means that the number of solutions is $O(N^3)$. 

To show that there are actually $\gg N^3$ solutions, choose 
$$
x \in [0.5 N, 0.55 N], \ y\in [2.6N, 2.8N], \ y\equiv x \bmod 2, \ u\in [0.45N,0.5N], \ u\equiv 0 \bmod 2.
$$
Then the second interval for $v$ is contained in the first. We need to count the number of $v$ in the second interval such that $v\equiv u \bmod 2$. 
The number of such $v$ is 
$$
\ge \left\lfloor \frac{xy}{2u} \right\rfloor -  \left\lfloor \frac{xy}{2u}-\frac{x-u}{2u} \right\rfloor 
= \frac{x-u}{2u} -\psi\left( \frac{xy}{2u} \right) + \psi\left( \frac{xy}{2u} -\frac{x-u}{2u}\right) ,
$$
where $\psi(t)=t-\lfloor t \rfloor -1/2$. Summing the $\psi$'s over $u$ results in $o(N)$, so their total contribution 
(after also summing over $x$ and $y$) is $o(N^3)$. 
Summing the term $(x-u)/(2u)$ over $u,x,y$ contributes $\asymp N^3$.