Find all values of $k$ so that the graphs of $x^2 + y^2 = 4 + 12x + 6y$ and $x^2 + y^2 = k + 4x + 12y$ intersect.  Enter your answer using interval notation.
Completing the square in the first equation, we get
\[(x - 6)^2 + (y - 3)^2 = 7^2,\]which represents a circle centered at $(6,3)$ with radius 7.

Completing the square in the second equation, we get
\[(x - 2)^2 + (y - 6)^2 = k + 40,\]which represents a circle centered at $(2,6)$ with radius $\sqrt{k + 40}.$

[asy]
unitsize(0.3 cm);

draw(Circle((6,3),7),red);
draw(Circle((2,6),2),blue);
draw(Circle((2,6),12),blue);

dot("$(6,3)$", (6,3), NE);
dot((2,6));
label("$(2,6)$", (2,6), NE, UnFill);
[/asy]

The distance between the centers is $\sqrt{4^2 + 3^2} = 5,$ so the two circles intersect when the radius of the second circle is between $7 - 5 = 2$ and $7 + 5 = 12.$  This gives us
\[2^2 \le k + 40 \le 12^2,\]or $k \in \boxed{[-36,104]}.$