O Perl pode fazer isso, mesmo em quebras de linha.
Coloque isso em um arquivo (eu chamarei de example.html):
<p>Here is some <span>foo bar</span> example text.</p>
<p>Some text even <span>foo
bar</span> spans across line breaks.</p>
Então experimente:
$ perl -0777 -pe 's/<span.*?<\/span>//gs' example.html
<p>Here is some example text.</p>
<p>Some text even spans across line breaks.</p>