Quick comparison

Simplify[123*(3*(2*x)^2 + 167*y^2*x + y*x + 4*y^3*x^2)]
(* 123 x (y (1 + 167 y) + 4 x (3 + y^3) *)

f[x_, y_] := 123 x (y (1 + 167 y) + 4 x (3 + y^3);

Table[If[TrueQ[Sqrt[f[x, y]] \[Element] Integers], {x, y}, Nothing], {x, 2000, 5000},
  {y, 2000, 5000}] // AbsoluteTiming // First
(* I gave up after waiting for 6 minutes *)

Table[If[sQ[f[x, y]], {x, y}, Nothing], {x, 2000, 5000}, {y, 2000, 5000}] // 
 AbsoluteTiming // First
(* 49.3531 *)

What is the definition of sQ[.]? Now it does not work in my Mathematica.