Você pode converter vídeos em upconverter, isso não aumenta a qualidade, mas aumenta o tamanho. Se não houver nada de qualidade equivalente ou superior para que ele seja resamplificado, não será possível criar uma qualidade "melhor". Você pode querer escolher um formato que tenha qualidade inferior se precisar de um tamanho de arquivo menor.
Quanto a um programa de vídeo que faz esse tipo de coisa: VideoDub foi incrível da última vez que o usei.