Existence (as mentioned on Wikipedia, for example), is easy, although not necessarily unique. Any unitary can be written as
$$
U=\sum_ie^{i\theta_i}P_i
$$
where $P_i$ are projectors such that $\sum_iP_i=1$, and $\theta_i$ is in the range 0 to $2\pi$. Then we have that
$$
\sqrt{U}=\sum_ie^{i\theta_i/2}P_i.
$$
Giving a circuit construction of the gate is an entirely non-trivial matter. There is no simply conversion that you can run on a circuit for a given $U$ to create a circuit for $\sqrt{U}$.
One method (even if you don't know anything about the $U$) is that if you can implement $U$ then you can implement controlled-$U$ (just replace all gates with their controlled versions. It's probably overkill, but is guaranteed to work). Then you can use those as part of a phase estimation. Apply a phase on the ancilla system corresponding to half the phase of the original unitary, and then apply the inverse of phase estimation. The details can be found here.
One simplification that you can make is that if
$$
U=VWV^\dagger,
$$
then
$$
\sqrt{U}=V\sqrt{W}V^\dagger,
$$
so if you have your circuit and can find a big section corresponding to $V$, you can remove it and just worry about implementing the square root of the remaining component $W$.
You'll notice that I'm not giving a proof that square roots are hard to come up with. It'll vary on a case by case basis. But think about the opposite task of creating integer powers of a unitary. Usually, we cannot do any better than repeated application of the original unitary. Just look at what you get in one of the very few special cases where you can compute higher powers more efficiently: you get Shor's factoring algorithm! (The point being that phase estimation becomes vastly more efficient.) If you could generically do better, you could apply phase estimation to Grover's search and you'd have a faster search algorithm.
