Are there Chinese language-learning karaoke videos at a basic conversation level?
Karaoke is more like combining the MV and lyrics together, most of them afford the instrumental version, which means that you can find them in Music Company. Of course, there is a faster way, if you know a karaoke store owner, he/she know how to get you a list of karaoke. 

FYI -
Most karaoke videos are properties of music companies, but due to some reasons lots of people have access to the pirate. So you might need to be cautious to avoid the legal issue.