Looking for the asymptotic expansion to as high order as possible of the sum $$S \left({m,n}\right) = \sum_{k = \lceil{\sqrt{n}}\rceil}^{\lfloor{m/2}\rfloor} \left[{\sqrt{{k}^{2} - n} \in \mathbb{Z}}\right]$$
where $\left[{...}\right]$ are the Iverson brackets and $m < n$ for positive integers $m$ and $n$, however for the solution we can consider $m \le n$. I do not suspect that there is an exact solution form. So I expect an asymptotic solution. Numerical testing suggests that for $m \rightarrow \infty$ we have $$S \left({m,n}\right) \sim \frac{1}{2} \log \left({m}\right)$$ I have not made any more progress.
Lets looks at a related problem (in my series): Define
$${S}_{2} \left({m, n}\right) = \sum_{j = \lceil{\sqrt{n}\rceil}}^{{j}_{max} + \lceil{\sqrt{n}\rceil}} \left[{\sqrt{{j}^{2} - \lceil{\sqrt{n}\rceil}^{2}} \in \mathbb{Z}}\right]$$
where ${j}_{max}=\lfloor{\sqrt{\lfloor{m/2}\rfloor^{2}+n}}\rfloor$. We can establish a lower bound for the this sum as follows, let $j = \lceil{\sqrt{n}}\rceil + \ell$ then
$$ \left[{\sqrt{{j}^{2} - \lceil{\sqrt{n}}\rceil^{2}} \in \mathbb{Z}}\right] = \left[{\sqrt{\ell \left({\ell + 2 \lceil{\sqrt{n}}\rceil}\right)} \in \mathbb{Z}}\right] $$
If ${x}_{1}\, {x}_{2}$ is a square, and $d = \gcd \left({{x}_{1}, {x}_{2}}\right)$, define ${y}_{i} = {x}_{i}/d$. Then ${x}_{1}\, {x}_{2} = {p}^{2} \rightarrow {y}_{1}\, {y}_{2} = \left({p/d}\right)^{2}$ and $k/d \in \mathbb{Z}$ by the Rational test. Since ${y}_{1}$ and ${y}_{2}$ are coprime factors of a square it follows that both are squares. Then if $\gcd \left({\ell, \ell + \lceil{\sqrt{n}}\rceil}\right) = 1$ for all $\ell$ the number of perfect squares between $\ell = 0$ and $\ell = {j}_{max}$ is $\lfloor{\sqrt{{j}_{max}}}\rfloor + 1$ with
$$ {S}_{2} \left({m, n}\right) \ge \lfloor{\sqrt{{j}_{max}}}\rfloor + 1 \sim \frac{1}{\sqrt{2}}\, \sqrt{m} - \frac{1}{\sqrt{2}}\, \sqrt{\frac{n}{m}} + {O} \left({\frac{1}{\sqrt{m}}}\right). $$
We are missing the counts when $\gcd \left({\ell, \ell + \lceil{\sqrt{n}}\rceil}\right) > 1$. So taking this into account would be the actual solution. The obvious crude upper bound is
$$ {S}_{2} \left({m, n}\right) \le {j}_{max} + 1 \sim \frac{m}{2} - \sqrt{n} + \left({\frac{n}{m}}\right) - \frac{1}{m} \left({\frac{n}{m}}\right)^{2} + {O} \left({\frac{1}{\sqrt{n}}}\right) + {O} \left({\frac{1}{{m}^{2}}}\right). $$
However the main condition on perfect square is that $\ell \left({\ell + \lceil{\sqrt{n}}\rceil}\right)\in \mathbb{Z}^{2}$, so assuming that ever perfect square between $\ell = 1$ and $\ell = {j}_{max}$ is a large over count. For example testing at $n = {10}^{6}$ and $m = 999{,}999$ then $S\left({999{,}999, {10}^{6}}\right) = 17$ while the number of cases where $\gcd \left({\ell,\ell + \lceil{\sqrt{n}}\rceil}\right) = 1$ and $\ell/gcd(...)$ and $\left({\ell + \lceil{\sqrt{n}}\rceil}\right)/gcd(...)$ are prefect squares is $2$. The lower approximation based on perfect square count between $\ell = 1$ and $\ell = {j}_{max}$ is $706$. So this is clearly not correct.
From the sum of two squares theorem, the number of representable numbers (sum of two squares) between $0$ and $n$ is proportional to $b\, n/\sqrt{\log \left({n}\right)}$ where $b = 0.76422365358922066299069873 \cdots$ is the Landau-Ramanujan constant. Thus we can refine the upper bound to be
\begin{equation*} {S}_{2} \left({m, n}\right) \le b\, \frac{{j}_{max}}{\sqrt{{j}_{max}}}. \end{equation*}
However, this includes all cases where a representable number can be written as a sum of two squares. In this case one of the squares is constant. So this is an over count. So far the current limits are $$\lfloor{\sqrt{{j}_{max}}}\rfloor + 1 \le {S}_{2} \left({m, n}\right) \le b\, \frac{{j}_{max}}{\sqrt{{j}_{max}}}$$
where the lower limit is not accurate.