Can the Legendre symbol be calculated in polynomial time?

For quadratic reciprocity, you need the Jacobi symbol. It's an extension of the Legendre symbol to composite $p$ that still satisfies quadratic reciprocity, so you can just apply quadratic reciprocity to your heart's content without worrying about primality. The Jacobi symbol does not generally tell you whether a number is a perfect square, so it doesn't have the same interpretation as the Legendre symbol, but it agrees with the Legendre symbol whenever $p$ is prime (so it will tell you the answer in your case, even though the intermediate results are a little strange).

However, Euler's criterion already works in polynomial time. You want to compute $a^{(p-1)/2}$ modulo $p$. As you observed, repeated squaring is a good way to deal with the fact that the exponent $(p-1)/2$ is large. Aside from that, you just need to do arithmetic modulo $p$, since you can reduce each intermediate calculation modulo $p$ before continuing. Thus, it can be done in polynomial time. (In your question, you said you need integers of length $p$, but it should be $\log p$.)