In Captain America: Civil War, it is revealed that
Bucky killed Tony Stark's parents.
How is it possible that there was any footage available of this event?
Did HYDRA always record such incidents on video?
Warning: Spoiler level over 9000. This is effectively the bulk of the plot that wasn't already revealed in the trailers.
If you had watched the movie to the end and paid attention to when the revelation was made,
the final screening of the footage showed the Winter Soldier shooting at the screen - an indication that this is a camera recording.
Most likely, the incident was captured by a speed camera that just happened to be there. Ordered to leave no witnesses, the Winter Soldier thus destroyed it. He likely reported this to his superiors when he returned - HYDRA would then recover the footage and cover up to prevent any leaks, though they did not, apparently, destroy all traces of the footage permanently.
The likely reason that Sokovian dude possessed the clip was because he hacked into SHIELD - formerly HYDRA's front for over half a century - and accessed its files to find something with which he could destroy the Avengers from within - and this clip is exactly what he needed.