Backpropagation Through Time (BPTT) of LSTM
Doesn't this dependency lead to the exploding/vanishing gradients problem again?


Absolutely, and you better have vanishing gradients otherwise you have a training problem. 

Vanishing gradient in this case is not a bad thing, it is a good thing (unlike in feedforward). Let $C(t)$ be the cost function evaluated at time $t$ and $ W(t)$ be some weight of the network at time $t$. What vanishing gradient in this case means is that $ dC(t)/dW(t-u)$ becomes smaller and smaller as u becomes bigger and bigger. That is good because $ dC(t)/dW =  \sum_{u=0}^{num\_steps} dC(t)/dW(t-u) $, so if the gradients didn't vanish in time, then the gradients would explode. So $W$ gets a proper non-vanishing gradient even if the gradients in time vanish because the gradient for $W$ is the sum at all times of the gradient for $W$. 

In LSTMs the gradients are sure to vanish in time because the activation functions are sigmoids and tanh's so their derivatives are less than or equal to one, so as they get multiplied they slowly become smaller. 

This compares to what is normally called the vanishing gradient problem which occurs when gradients vanish while passing from top layers to bottom layers, because that means that $ dC/dW $ for $W $ of the lower layer is vanishing and so the lower layers don't get trained, only the upper layers get trained. 

Also, as mentioned in the comments, the above applies to any RNN, not only LSTMs. What sets LSTMs appart from vanilla RNNs in with regards to this question is the gating functions which allows the LSTM to control what it remembers and what it forgets and how much of the new input it takes in. While the above is true in practice for LSTMs (and is true on average also in theory), in theory, one could have a time step $t$ where the output has ignored the last 10 inputs and only depends on the input 11 timestep back ($t-11$), in which case the gradient for the weights 11 timesteps ago will not have decayed. Of course that means that at the next time step ($t+1$) the gradients for 11 steps ago ($t+1 -11 = t-10$) will be zero because the input was totally disregarded at $t-10$. So on average it averages out and you still have the same situation for LSTMs.