If they were independent, it would be impossible:
E(X + Y) = E(X) + E(Y) if X and Y are independent.
(where E(X) = E(x | X=x) is the expected value of a random variable). This is easily provable:
E(x | X = x) = \integral_{-\inf}^{inf} x f_X(x) dx, and by integration by parts:
\integral_{-\inf}^{inf} \integral_{-\inf}^{inf} (x + y) f_X(x)f_Y(y) dx dy = \integral_{-\inf}^{inf} f_Y(x) \integral_{-\inf}^{inf} x f_X(x) dx dy + \integral_{-\inf}^{inf} f_Y(y) \integral_{-\inf}^{inf} x f_X(x) dy dx = \integral_{-\inf}^{inf} f_Y(y) dy \integral_{-\inf}^{inf} x f_X(x) dx + \integral_{-\inf}^{inf} f_X(x) dx \integral_{-\inf}^{inf} y f_Y(y) dy
Since p.d.f.s f_X(x) integrate to 1 over their domain,
\integral_{-\inf}^{inf} f_Y(y) dy \integral_{-\inf}^{inf} x f_X(x) dx + \integral_{-\inf}^{inf} f_X(x) dx \integral_{-\inf}^{inf} y f_Y(y) dy = \integral_{-\inf}^{inf} x f_X(x) dx + \integral_{-\inf}^{inf} y f_Y(y) dy = E(X) + E(Y)
Therefore, if two games are independent, the expected loss is the sum of the expected losses. For real-valued expected losses, it is not possible to add two real numbers of the same sign and get a real number of the opposite sign, and so the 'paradox' is therefore impossible for independent games.
But you are right, for non-independent games, it doesn't seem that surprising, so it doesn't really meet the definition of a paradox.
Linearity of expectation applies to any two random variables, not just ones that are independent. The issue is that these games are not random variables, they are random processes (sequences of random variables) with state affected by the choices you make and previous outcomes. Linearity of expectation is irrelevant.
\integral_{-\inf}^{inf} f_Y(y) dy \integral_{-\inf}^{inf} x f_X(x) dx + \integral_{-\inf}^{inf} f_X(x) dx \integral_{-\inf}^{inf} y f_Y(y) dy = \integral_{-\inf}^{inf} x f_X(x) dx + \integral_{-\inf}^{inf} y f_Y(y) dy = E(X) + E(Y)
Therefore, if two games are independent, the expected loss is the sum of the expected losses. For real-valued expected losses, it is not possible to add two real numbers of the same sign and get a real number of the opposite sign, and so the 'paradox' is therefore impossible for independent games.
But you are right, for non-independent games, it doesn't seem that surprising, so it doesn't really meet the definition of a paradox.