Consider two paraboloids. The first one is given by $x^2 + y^2 = z+5$. So, it intersects the x-y plane in the circle $x^2+y^2=5$. The second paraboloid is exactly the same as the first one, only shifted in the x-y plane. It's equation becomes $(x-1)^2+(y-1)^2=z+5$. From the figure below, it seems clear that the two should intersect in a parabola.
However, when we actually try and solve the two equations simultaneously, we get from the second equation $$x^2 + y^2 -2x - 2y + 2 = z+5.$$ And substituting $x^2+y^2=z+5$ into this we get $$2x+2y=2.$$
Now this is a linear function. However, the picture seems to suggest that it should be a parabola which is non-linear. What am I missing here?

What you have obtained is the equation of the plane containing the intersection parabola.
The parabola in cartesian form is indeed defined by two different equations, as the following
$x^2+y^2=z+5$
$x+y=1$
You can parametrize it by