Passo 1: Extraia todos os quadros do arquivo gif de entrada (usando imagemagick)
convert INPUT.gif gif%05d.png
Etapa 2: converter quadros em vídeo
ffmpeg -r FRAMERATE -i gif%05d.png -y -an OUTPUT.mp4
Etapa 3 (opcional): exclua todos os arquivos temporários desnecessários
rm gif*.png
Tome cuidado ao excluir arquivos.
Edit: Em algumas versões do Ubuntu e Debian ffmpeg foi substituído por avconv , mas a sintaxe continua a mesma.