Solution:
Let $m = 503$ and $n = 4m + 1 = 2013$.
Note that
$$(m-1)n = (m-1)(4m+1) < m \cdot 4m = (2m)^2 < m(4m+1) = mn$$
so the perfect square $(2m)^2$ is in the $m$-th row.
Note that $(k+1)^2 - k^2 = 2k + 1$ is at most $n$ if $k \leq 2m$ and is at least $n$ if $k \geq 2m$. Therefore, on the one hand, the first $2m+1$ perfect squares never skip a row and the first $m+1$ rows are all deleted. On the other hand, the last $n - (2m-1) = 2m + 2$ perfect squares are in pairwise distinct rows.
Thus, the first $m+1$ rows and $2m$ more are deleted, so $m$ rows remain.
The $j$-th column is deleted if and only if $j$ is a square modulo $n = 2013 = 3 \cdot 11 \cdot 61$. By the Chinese Remainder Theorem, this is the case if and only if $j$ is a square modulo each of $3$, $11$, and $61$. Since the numbers of squares for these three moduli are $2$, $6$, and $31$ respectively, the number of squares modulo $n$, again by the Chinese Remainder Theorem, is $2 \cdot 6 \cdot 31 = 372$. The number of remaining columns is therefore $2013 - 372 = 1641$.
The number of remaining cells is $503 \cdot 1641 = 825423$.