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 *)
