For the 5-7kV ones, I strongly suspect, as someone has already suggested, it'll be a flyback, royer, or self oscillating step up transformer, possibly followed by a voltage multiplier if the output is said to be 'DC'. You can get 5-7kV directly out of a transformer but will either be just high frequency AC (royer), or short pulses (flyback).
For that one in the video, as I said, its output voltage will be dependent on the spark gap. If the output wires are far enough from each-other, then what limits its 'output voltage' is the breakdown of the internal insulation of the output transformer. This is also the case for stun guns. And yes, the figures provided are overblown and probably never tested, just marketing - although if the output transformers insulation is good enough, and the output electrodes far enough apart, I'm sure extremely high voltages are possible, but certainly never regulated.
Their only real purpose is to make big fat scary arcs to impress/scare people, to ignite gas/fuel, or to cause pain. The old 'proper' stun guns designed to temporarily paralyze used specific (albeit not very accurate) timing of pulses, with a controlled current and voltage limit (voltage was limited by an internal spark gap). Modern ones are just nasty high voltage pulsers with short output pulses, but at very high power.
So ultimately, china just knocks these out for the novelty factor - who doesn't love high voltage arcs? But in practical terms, powerful pulsed arcs like that can easily interfere with nearby electronics, can be very loud, produce ozone... burn/melt your arcing wires so it doesn't really have much practical use. I'll probably still buy one though as they're so cheap!