Given the letter artifacts in "Kill Bill" it looks like they're preserving vertical position. So, possibly making each vertical pixel stripe a horizontal average of several consecutive frames---all pixels at height y in an adjacent batch of a few dozen frames.
If I was to do it I would take every digital frame and then take each pixel from top left to bottom right and make one long chain. Either that or average x neighboring pixels to fit the size vertically. I have no idea how they did this specifically though.
A discussion using mplayer for faster output is also attached at http://projects.metafilter.com/2996/Make-your-own-Movie-Barc...