The Demon's memory store acts like an entropy reservoir. In the process of measuring the speed of each molecule, the Demon reproduces the random pattern of fast and slow gas molecules on either side of the barrier in the memory store, so the entropy for the entire system is exactly the same. When the Demon deletes the data, it is returning it from $2^n$ states to one state, and thus reducing the entropy in exactly the same way as separating the gas molecules would.
For the sake of illustration, let's suppose the Demon is using an abacus to store the data. Initially, the gas is in one of $2^n$ states, while the abacus (initially empty) is in one of one possible states. We have $n$ bits of entropy.
Now the demon measures the speed of each molecule and checks it against the threshold, gaining one bit of information per measurement. It uses this information to sort the molecules. So now the gas is in one of only one possible states, and the abacus is in one of $2^n$ possible states, exactly reproducing (the relevant part of) the initial state of the gas. We can think of the beads on the abacus wires as molecules in one of two compartments, at the top and bottom of the abacus.
The number of states of the system as a whole (gas + Demon) is exactly the same: $2^n$. The process is reversible. The entropy has neither increased nor decreased, the 2nd law of thermodynmamics has not been violated.
When the information is deleted, the Demon has to go through the beads, check whether it is at the top or bottom of the wire, and push it in the appropriate direction to cancel out the information. It is doing exactly the same sort of task as it was in sorting the gas molecules - going from one of $2^n$ states to a single defined state. And so, for exactly the same reason, it has to tranfer the information gained from looking at each bead-bit somewhere else, into some other reservoir of entropy.
