Try
Karafun, although there are various different karaoke formats, this one supports most of them. You of course need the tracks as well as the software to play them. These can be bought online, or created yourself using MIDI files and the included editor, along with the freely available lyrics.
