Pilaf gang made the wish just before Piccolo were killed by the androids.
Toriyama's Dragon Ball manga and both Dragon Ball Z and Dragon Ball Super anime adaptations didn't cover that event IIRC, but Toyotaro did in a special chapter of his manga (in Vol. 2). According to Dragon Ball Wiki:
In the future timeline, Future Android 17 and Future Android 18 ...
The song is 究極の聖戦 (kyūkyoku no battle in romaji or Ultimate Battle in english). There are two versions of this song:
The one performed by Akira Kushida (the version Shazam found)
The one without vocals (the version you are looking for)
According to Anison, the version without vocals is named 究極の聖戦 (カラオケ) (where "カラオケ" means "karaoke").
I searched on ...