Hint: It is well known that $(a+b+c)^2 \geq 3 (ab+bc+ca)$, with equality when $ a = b = c$.
Further hint, (actually the crux in this approach, so I encourage you to think about how the previous line could be a hint. If you don't know what to do, I suggest to skip this part first and read the rest of the solution below the separator):
Set $ a = x_1 + x_4, b = x_2 + x_5, c = x_3 + x_6$.
Hence $ C = 3$.
Steps that one could take to approach the inequality directly:
Setting $ x_i = 1$ gives $ C \leq 3$. A reasonable guess is that $ C = 3$ is the answer (though this need not be the case).
Notice that with $C=3$, equality holds when $ x_1 = x_3 = x_5 , x_2 = x_4 = x_6$, so it's not a standard "all terms equal" scenario.
Calling the term on the RHS $X$ (without the constant), show that $$X = (x_1 + x_4) ( x_2 + x_5) + (x_2 + x_5) ( x_3 + x_6) + (x_3 + x_6) ( x_1 + x_4).$$ Arguably, this is a "nicer" expression.
$$(x_1 + x_2 + x_3 + x_4+ x_5 + x_6) ^2 - 2X = (\sum x_i^2) + 2 ( x_1x_4 + x_2x_5 + x_3x_6) \geq X.$$
Equality holds when $x_1 + x_4 = x_2 + x_5 = x_3 + x_6$.
Hence $(x_1 + x_2 + x_3 + x_4+ x_5 + x_6) ^2 \geq 3X$
Hence, the answer is $C = 3$.
From here, it's easy to motivate the original substitution.