Other Graphics Software
Karaoke Animator
Lugn Karaoke Animator is a free Android app to create karaoke videos. It has a very limited feature set, but it can generate up to 1080p 60fps karaoke with only a cellphone.
Karaoke Lyric Editor
Karaoke Lyric(s) Editor is free/open source software for Windows, Mac, and Linux to create karaoke tracks. It can import multiple formats and export both CDG and video. While it is free, it recommends a paid registration which includes support. It can be finicky, and is difficult to get a reasonable-looking CDG out of it due to the way it scales text. It also does not have a lot of layout options, and has an unusual style of lyric wiping that highlights a character at a time instead of progressive wiping.
Aegisub
Aegisub is a free/open source and multi-platform subtitle editor that supports the Advanced Substation Alpha (.ass) format, thus allowing for karaoke features. It is possible to create karaoke with it directly, though it is tedious. Karaoke Mugen has a doc on how to do so using their process: Create a Karaoke
Aegisub can also be useful for editing .ass files generated by kbp2ass or The Tüül, to fine-tune formatting or add effects.
Video Editors
Some people create their karaoke videos directly in a regular video editor without any karaoke-specific features. This typically means drawing the text on a layer and creating a wipe layer to change the color of the text. It can be very tedious, though copy/paste can help if there is enough repetition in the song, and it provides the maximum flexibility in layout, effects, wipe style, etc.
Walkthrough from Hal Jam:
MyKaraoke Video
MyKaraoke Video is still new to the game so doesn’t have a lot of features yet, but it’s easy to use and can create 1080p karaoke videos including background video or images.