I here is a proof.
Note first, that the six points lie on a conic. Indeed, the opposite sides of the "hexagon" $P_{12}$, $P_{32}$, $P_{34}$, $P_{52}$, $P_{56}$, $P_{16}$ intersect again in points $A, B, C$, which lie on one line. Hence they lie on a conic by the converse to Pascal's theorem. So, we only need to prove that this conic is a circle.
Next, let's do the same thing as what is done when one deduces Pascal's theorem from Bezout. Consider cubic polynomials $F_{red}=L_1\cdot L_3\cdot L_5$, $F_{blue}=L_2\cdot L_4\cdot L_6$, $ F_{red}'=L_1'\cdot L_3'\cdot L_5'$ that are product of linear polynomials $L_i$ and $L_i'$ such that $L_i=0$ defines $l_i$ and $L_i'=0$ defines $l_i'$. Finally, let $L$ be the linear polynomial that vanishes at $A,B,C$.
From Bezout theorem it follows that for a unique value of $c$, $F_{red}+cF_{blue}$ is divisible by $L$ and $\frac{F_{red}+cF_{blue}}{L}=0$ is the equation of the original circle. And also for some $c'$, $F_{red}'+cF_{blue}$ is divisible by $L$. I claim that $c=c'$. If this is proven, then the desired statement is proven, because by the assumptions, the cubic term of $F_{red}'$ coincides with the cubic term on $F_{red}$ (indeed, their zeros a two triples of parallel lines). So it would follow that $\frac{F_{red}+cF_{blue}}{L}$ and $\frac{F_{red}'+cF_{blue}}{L}$ have the same quadratic term, and so both define circles.
So, it remains to show that $c=c'$. Let us denote by $\bar F_{red}$, $\bar F_{red}'$, $\bar F_{blue}$ the cubic terms of $ F_{red}$, $\ F_{red}'$, $ F_{blue}$. Let $\bar L$ be the linear term of $L$. Note that both $\bar F_{red}+ c\bar F_{blue}$ and $\bar F_{red}'+ c'\bar F_{blue}$ are divisible by $\bar L$. However, as we saw above $\bar F_{red}=\bar F_{red}'$. It follows that $c=c'$. QED.