Deleting documents only flags these as deleted, so they would not be searched. To reclaim disk space, you have to optimize the index:
curl -XPOST 'http://localhost:9200/_optimize?only_expunge_deletes=true'
documentation: http://www.elasticsearch.org/guide/en/elasticsearch/reference/current/indices-optimize.html
The documentation has moved to:
https://www.elastic.co/guide/en/elasticsearch/reference/current/indices-forcemerge.html
Update
Starting with Elasticsearch 2.1.x, optimize is deprecated in favor of forcemerge.
The API is the same, only the endpoint did change.
curl -XPOST 'http://localhost:9200/_forcemerge?only_expunge_deletes=true'