There are 372 quadratic residues mod 2013, so 372 columns will be deleted. For $n \leq 1005$, $(n+1)^2-n^2 < 2013$ so each interval $[m + 1, m + 2013]$ such that $m + 2013 \leq \displaystyle\lceil{1005^2/2}\rceil=502\cdot 2013$ contains at least one square, for $502$ rows. Since $(n+1)^2-n^2 \geq 2013$ for larger $n$, $1006^2,1007^2,\ldots,2013^2$ are in different rows, for a total of $502 + 1008=1510$ rows. Accounting for the $372\cdot1510$ common elements, $(372+1510)2013-372\cdot1510$ elements are removed.

Nice solution