Is using Euler's Totient/phi in Tonelli-Shanks (used to recover EC coordinate) safe? I'm implementing an algorithm in order to recover the $y$ co-ordinate from $x$ in order to construct a co-ordinate pair that satisfies secp256k1's elliptic curve equation, which is:
 $y^2 = x^3 + 7 \bmod q$.

$q$ is a prime and $q \equiv 3\bmod 4$ (I've checked) so we should be able to use:

$y = (x^3 + 7 \bmod q)^{\frac{q+1}{4}}.$

However, the size is limited to 256 bits and so $\frac{q+1}{4}$, which I'm calculating by $(q+1) \times 4^{-1}$, will be taken modulo $256$. I'm scared of this making the overall result wrong, so I was thinking of using Euler's totient and taking $\frac{q+1}{4} \bmod (q-1)$, as $\phi(q) = q-1$ due to $q$ being prime.

Is this safe? I can't find it recommended anywhere and I feel like it would be a good optimisation if it was actually safe to use, and so would be noted somewhere?
As user94293 says, $q\equiv 3\bmod4 \implies q+1\equiv0\bmod 4$ hence $\frac{q+1}{4}$ is an integer. Clearly it is smaller than $q$ and larger than $0$, hence reducing it mod $q-1$ does not change anything. Hence in your circumstance everything is okay.

In a bit of a more broad context, determining whether something is "safe to use" depends on context. What can generally go wrong is that execution time of an algorithm is dependent on some secret data. An attacker will exploit this timing dependency to gain information about the secret, which is indeed a problem. So in this case you can ask yourself two more general questions:


What information could an attacker learn if you were to compute $$\left(x^3+7\right)^{\frac{q+1}{4}\bmod{q-1}}\bmod{q}$$ as opposed to
$$\left(x^3+7\right)^{\frac{q+1}{4}}\bmod{q}?$$
As long as you don't compute either one or the other depending on some secret, both are fine. Note that this includes that we could choose to compute a square root by doing 
$$\left(x^3+7\right)^{\frac{q+1}{4}+1000(q-1)}\bmod{q},$$
but we won't because it is not efficient.
What data is actually being processed? I'm not aware of the details of the protocol you are working with, but in many cases $x$-coordinates of points are part of public data. In that case even if you do the exponentiation based on the value of $x$, an attacker can still not learn anything secret.


In short, it is important to remember that it is not important for an algorithm to be constant time, but to have run-time independent of secret data.