Find deleted files in Mercurial repository history, quickly?

using templates is simple:

$ hg log --template "{rev}: {file_dels}\n"

Update for Mercurial 1.6

You can use revsets for this too:

hg log -r "removes('**')"

(Edit: Note the double * - a single one detects removals from the root of the repository only.)

Edit: As Mathieu Longtin suggests, this can be combined with the template from dfa's answer to show you which files each listed revision removes:

hg log -r "removes('**')" --template "{rev}: {file_dels}\n"

That has the virtue (for machine-readability) of listing one revision per line, but you can make the output prettier for humans by using % to format each item in the list of deletions:

hg log -r "removes('**')" --template "{rev}:\n{file_dels % '{file}\n'}\n"

If you are using TortoiseHg workbench, a convenient way is to use the revision filter. Just hit ctrl+s, and then type

removes("**/FileYouWantToFind.txt")

**/ indicates that you want to search recursively in your repository. You can use * wildcard in the filename too. You can combine this query with other revision sets using and, or operators.

There is also this Advanced Query Editor: