$ git br -r | awk -F/ '/^[[:space:]]+origin/ {print $2}' \
| xargs git push --delete origin

awk の regex で \s とかが使えなかった。

追記1

長いけど、grepで絞った方がわかりやすいかとおもいました。

$ git br -r --merged | grep -e '\sorigin\/' | awk -F/ '{print $2}' \
| xargs git push --delete origin

追記2
<pattern> が使えました。この場合は --list の明示が必須です。

$ git branch -r --list 'origin/*' | awk -F/ '{print $2}' \
| xargs git push --delete origin

いまのところこれが一番すきです。

参考

ftp://ftp.gnu.org/old-gnu/Manuals/gawk-3.0.3/html_chapter/gawk_5.html

補足

$ g push --delete origin test
error: unable to delete 'test': remote ref does not exist
error: failed to push some refs to 'git@github.com:mochizukikotaro/hoge.git'

こんなエラーになってしまったときは、以下。（リモートリポジトリで直接消すとこうなるらしい）

$  git remote prune origin