Answer: 85

Solution:

Write $P(x) = x^2 + px + q$ with roots $r_1$ and $r_2.$ The solutions of $P(P(x)) = 0$ split into the two solutions of $P(x) = r_1$ and the two of $P(x) = r_2,$ and each pair sums to $-p.$

If $3$ and $4$ form one pair, then $a + b = -p = 3 + 4 = 7,$ so $(a + b)^2 = 49.$ This is achievable: $P(x) = (x - 3)(x - 4) + r_1$ with $r_1$ satisfying $r_1^2 - 6r_1 + 12 = 0,$ which has (complex) solutions, and the four roots are distinct.

Otherwise $3$ and $4$ lie in different pairs: $3 + a = 4 + b = -p = s,$ and $\{P(3), P(4)\} = \{r_1, r_2\}.$ The root sum gives $P(3) + P(4) = 25 + 7p + 2q$ $= s,$ so with $p = -s$ we get $q = 4s - \frac{25}{2},$ and then $P(3) = s - \frac{7}{2}$ and $P(4) = \frac{7}{2}.$ The root product gives $\frac{7}{2}\left(s - \frac{7}{2}\right) = q = 4s - \frac{25}{2},$ whose solution is $s = \frac{1}{2}.$ Then $a + b = (s - 3) + (s - 4) = -6,$ so $(a + b)^2 = 36,$ with $a = -\frac{5}{2},$ $b = -\frac{7}{2}$ all distinct from $3$ and $4.$ The sum of all possible values is $49 + 36 = 85.$