Why can't music recognition services like Shazam or SoundHound recognize music if its speed is changed by more than 5 percent?
this is a guess from someone who does audio, but has never ever done recognition nor watermarking algorithms for someone in the industry (but i have a little idea how they may be done).

my guess is that they extract some features from the STFT of the music.  associated with each feature is an envelope that represents the quantity of that feature at the center window time of the STFT.

the collection of those envelopes can be thought of as a point in a metric space.  if you have a metric space, you can define a difference function

$$ \| \mathbf{X} - \mathbf{X}_n \| $$

between those of any pair.

then they compare the test envelope, $\mathbf{X}$, with each template, $\mathbf{X}_n$, of a set that come from the original targets (the copyrighted songs they're fishing for).  there is a norm taken of the difference between these points in a metric space, between the collection of envelopes taken from the test sound and the template.  if the norm is below a given threshold and if the norm is the minimum compared to all of the templates, then the song of that best matching template is identified as matching the input or test sound.

now if the pitch is wrong it won't match as good.  but they could make their difference algorithm insensitive to a constant offset to pitch.  it's like running the difference signal through a DC blocking filter before calculating the norm of it.  but they would have to do that, otherwise a constant pitch difference between test tune and target will always be an error.

and they could match a tempo difference, but that is much harder.  if memory and computational effort is not a problem (and they often are not for non-realtime applications running on a GHz-speed computer or server) then there could be a template for each of many speeds.  and see which one matches best.  but if these other tempo templates do not exist, and you submit a tune that does not exactly match a template of it at the original speed, then at some point in the tune or song, the pitches will not match at all.  that will make a dumb algorithm think they're different tunes.