The relative sign of CGs is fixed by the recursion relation but the overall sign of all CGs is determined by the Condon-Shortley convention. To see this clearly, consider the singlet state constructed from two spin-1/2 states:
\begin{align}
\vert 00\rangle=\textstyle\frac{1}{\sqrt{2}}\vert \textstyle\frac{1}{2}\frac{1}{2}\rangle\vert \textstyle\frac{1}{2},-\frac{1}{2}\rangle -
\frac{1}{\sqrt{2}} \vert \textstyle\frac{1}{2},-\frac{1}{2}\rangle
\vert \textstyle\frac{1}{2}\frac{1}{2}\rangle \tag{1}
\end{align}
is just equally valid as a singlet state as
\begin{align}
\vert 00\rangle’=-\textstyle\frac{1}{\sqrt{2}}\vert \textstyle\frac{1}{2}\frac{1}{2}\rangle\vert \textstyle\frac{1}{2},-\frac{1}{2}\rangle +
\frac{1}{\sqrt{2}} \vert \textstyle\frac{1}{2},-\frac{1}{2}\rangle
\vert \textstyle\frac{1}{2}\frac{1}{2}\rangle\, ,
\end{align}
since the state $\vert 00\rangle’$ is killed by $L_+$, and is orthogonal to $\vert 10\rangle$.
More generally, the choice $-\vert JJ\rangle$ is as valid as $\vert JJ\rangle$, as far as being killed by $L_+$ and orthogonality with other states.
Hence, to determine the symmetry under exchange $(j_1m_1)\leftrightarrow (j_2m_2)$, it is sufficient to construct the compare the sign of the CGs
$C^{JJ}_{j_1j_1;j_2,J-j_1}$ and $C^{JJ}_{j_1,J-j_2;j_2j_2}$. It’s not hard to see that there are $j_1+j_2-J$ steps between these values when recursively solving $L_+\vert JJ\rangle=0$, and the Clebsch’s alternate in sign, so $(-1)^{j_1+j_2-J}$ comes out of that.
To get those CGs with $J$ interchanged with $j_1$ or $j_2$, we need to consider the integral relations between group functions:
\begin{align}
\int d\beta \, \sin\beta \, d^{J}_{JM’}(\beta) d^{j_1}_{j_1m_1’}(\beta)
d^{j_2}_{J-j_1;m_2’}(\beta)&=C^{JJ}_{j_1j_1;j_2,J-j_1}C^{JM’}_{j_1m_1’;j_2m_2’}\frac{2}{2J+1} \tag{2}\\
&=C^{j_1j_1}_{JJ;j_2,J-j_1}C^{j_1m_1}_{JM’;j_2m_2’}\frac{2}{2j_1+1}
\tag{3}
\end{align}
Since the $d^j$ functions are real, one can readily interchange the role of
$d^{J}_{JM’}(\beta)$ and $d^{j_1}_{j_1m_1’}(\beta)$ in (2) without changing the left hand side of (2), but changing the CGs and the factor $2/(2J+1)$ on the right to become (3). That’s the origin of the $\sqrt{2J+1/2j_1+1}$ factor in the interchange of argument of the CGs. Since the CGs of the type $C^{JJ}_{j_1j_1;j_2m_2}>0$ by the Condon-Shortley phase convention, the overall sign connecting the CGs with $J$ and $j_1$ exchanged comes out of evaluating directly the integral on the LHS of (2). The integral is somewhat simplified because
\begin{align}
d^{J}_{JM}(\beta)= \sqrt{\frac{(2J)!}{(J+M)!(J-M)!}}\cos(\beta/2)^{J+M}
\left(-\sin(\beta/2)\right)^{J-M}
\end{align}
although the general form of $d^{j_2}_{m_2m_2’}(\beta)$ is quite messy. Intuitively, it’s clear that the phase can only depend on $j_2$ and $m_2$, i.e. on the values of angular momenta that are not interchanged.
