Ian Mackinnon found the answer, but it's better with xargs:
git ls-files --deleted -z | xargs -r0 git rm
As a git alias:
git config --global alias.rm-deleted '!git ls-files --deleted -z | xargs -r0 git rm'
This uses xargs with NUL termination (the only byte guarranteed not to appear in a path) and the option to not run git rm
if the file list is empty.
This syntax is also fish compatible.