I claim that there is an $N$ so that any rectangle with both sides at least $N$ can be decomposed into squares of sides $4,5,7$ and $9.$ If we show that, then the same applies squares of sides at least $N.$ I will show this for $N=1178.$ With a little more work that number could be decreased to $123$. But that is probably far from optimal.
Let $a,b>0$ be relatively prime integers.
It is a result of Frobenious that any integer $m\geq f(a,b)=ab-a-b+1$ can be written in the form $m=as+bt$ with $s,t$ non-negative.
Using just $a\times a$ squares we can make a rectangle $a\times ab$ and using just $b \times b$ squares we can make a rectangle $b \times ab.$ Using those blocks we can make a rectangle $m \times ab$ for any $m\geq ab-a-b+1$
Hence
- Using $4 \times 4$ and $5 \times 5$ squares we can make a rectangle $20 \times m$ for $m \geq f(4,5)=12.$
-Using $7 \times 7$ and $9 \times 9$ squares we can make a rectangle $63 \times m$ for $m \geq f(7,9)=48$
- Using all four sizes of squares we can make any rectangle $m \times n$ provided that $m \geq 48$ and $n \geq f(20,63)=1178.$