I understand that Experience Replay is used for data efficiency reasons and to remove correlations in sequences of data. How exactly do these sequences of correlated data affect the performance of the algorithm?
It is the neural network approximation that suffers, when it attempts to learn from correlated data. Intuitively, this is because the learning algorithm takes gradient steps assuming that the examples it are shown are representative of the dataset as a whole. A neural network update step uses a mini-batch of examples to calculate the gradient of its weights and biases with respect to a cost function. If that mini-batch is not fairly sampled, then the expected value of the loss and of the gradient will not be representative of the population as a whole. They will be biased and can cause an update step to parameters in the wrong direction.
In addition, if you are using a bootstrapping method - any form of TD learning - then the value estimates used to set learning update targets are sensitive to bias in the estimator. This is already something that can cause instability due to positive feedback loops. Adding another source of systemic bias from correlated input data can only make it worse.
You can gain some experience for the effect of this with a simple non-RL experiment.
Goal: To approximate the function $y = x^2$ in the range $-2 < x < 2$. These numbers chosen to make the task simple for a neural network.
Setup: Generate training data in the form $x_i, y_i$ for a few thousand sample points with true values of the function. Optionally add some noise to make the task harder. Keep the data set ordered by $x_i$ values. Create a simple neural network for regression (e.g. 2 hidden layers with 50 neurons and tanh activation), and set it up with a simple optimiser (e.g. SGD)
Run: Train the network twice, using small minibatches (e.g. size 10). Once without shuffling the data on each epoch (or using any shuffling algorithm on the minibatches), and once with standard shuffling and assignment to minibatches. Plot a learning curve of loss vs epoch for each run.
You should find that the ordered, non-shuffled version learns much slower than when using some randomisation to decorrelate the data. Depending on precise hyperparameters, the ordered version may even oscillate with loss quite far away from converging.
It is this effect, or a more subtle version of it, that impacts RL combined with neural networks when learning direct from trajectories. In addition, there is existing starting bias in bootstrap methods, which this effect makes worse.