Looking at Haskell's Data.Sequence, it looks like it's strict in its elements. So a delete does free up memory as long as the deleted object isn't being used somewhere else.