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.$

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,6$ and $7.$ 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 $90.$ Although that is probably not 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 f(a,b)=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.$

Sticking to squares and rectangles which can be decomposed into vertical rows each of which itself can be decomposed into horizontal columns of widths $4,5,6,7$ or $9$ (with the further restriction that each row uses only two widths) , is probably far from optimal. However, by the method above we can get

• Any row $2x \times 2y$ with $\min(2x,2y) \geq 12$ using $(a,b)=(4,6).$
• Any row $3x \times 3y$ with $\min(3x,3y) \geq 18$ using $(a,b)=(6,9).$
• Any row $ab \times m$ with $m \geq f(a,b)=ab-a-b+1$ for any of the eight relatively prime pairs drawn from $\{4,5,6,7,9\}$

Ignoring the first two types, we can get any rectangle $p \times q$ with with $p \in \{20,28,30,35,36,42,45,63\}$ and $q \geq 48.$

Combining those we can get any rectangle $r \times q$ with

$r \in \tiny{\{ 20, 28, 30, 35, 36, 40, 42, 45, 48, 50, 55, 56, 58, 60, 62, 63, 64, 65, 66, 68, 70, 71, 72, 73, 75, 76, 77, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88\}}$ or $r \geq 90$ and $q \geq 48.$