You have another edge case too: 'fred=abcdef&wilbur=123456&wilfred=hijk' What you want is to make sure the $tag=(.*?) part is preceded by & or the beginning of the string and followed by & or the end of the string. This looks like:

s{(?:(?<=&)|^)
  $tag=(.*?)
  (?:(?=&)|\z)
...
[download]

where (?<=&) and (?=&) are zero-width positive look-ahead and look-behind assertions. It can be simplified using negative assertions, at the cost of making it a little hard to wrap your head around initially, to:

s{(?<![^&])
  $tag=(.*?)
  (?![^&])
...
[download]

(Literally, match $tag=(.*?) only when not preceded or followed by a non-& character.)