Если вы можете гарантировать, что ваш XML - который может иметь произвольную форму - находится в точной форме, которую вы написали, awk или perl могли бы выполнять работу намного проще, чем sed. У Unicornaddict было что-то, что сработало бы, но я бы был немного осторожнее в строке замещения:
perl -pe '$i++; s{id=""}{id="$i"} if /^<mytag id="">/' filename.xml
Если вы не можете гарантировать, что XML не имеет произвольной формы, вам действительно нужно проанализировать его с помощью правильного синтаксического анализатора XML. Обобщенный XML не может быть проанализирован с помощью регулярных выражений.