Substitution might help

From $(x+1)(y+1) = xy + x + y + 1 = 40$ , $\implies xy = 39-(x+y)$ . Then we have:

$\begin{aligned} xy(x+y) & = 380 \\ (39-(x+y))(x+y) & = 380 \\ (x+y)^2 - 39(x+y) + 380 & = 0 \\ (x+y -19)(x+y-20) & = 0 \\ \implies x+y & = \begin{cases} 19 \\ 20 \end{cases} \end{aligned}$

Then we have $x^2 + y^2 = (x+y)^2 - 2xy = (x+y)^2 - 2(39-(x+y)) = \begin{cases} 321 & \text{for }x+y = 19 \\ 362 & \text{for }x+y = 20 \end{cases}$ .

Therefore, the sum of all possible of $x^2+y^2$ is $\boxed{683}$ .

If we expand and simplify the first equation we get:

$\begin{cases} xy+x+y=39 \\ xy(x+y)=380. \end{cases}$

Let $S=x+y$ and $P=xy$ . The equations become:

$\begin{cases} S+P=39 \\ SP=380. \end{cases}$

Substituting $P=39-S$ into the second equation, we get $S(39-S)=380 \implies S^2-39S+380=0 \implies (S-20)(S-19)=0 \implies S=20 \text{ or } S=19.$

Substituting these values of $S$ into $S+P=39$ , we get that $(S,P)=(19,20) \text{ or } (20,19)$ .

Finally, $x^2+y^2=(x+y)^2-2xy=S^2-2P$ , so it could be $19^2-2(20)=321$ or $20^2-2(19)=362$ . The answer is $321+362=\boxed{683}$ .