Para teres um efeito de `fade` não podes ter `display: none;` pois o CSS não faz transição de `display`. Sugiro que faças isso com uma classe de CSS, onde mudas a _opacidade_ e escolhes a velocidade da animação.

Podes fazer assim:

    function Mudarestado(el) {
        document.getElementById(el).classList.toggle('mostrar');
    }

e no CSS defines a animação:

    #formulario {
        opacity: 0;
        transition: opacity .5s;
    }
    #formulario.mostrar {
        opacity: 1;
    }

###Exemplo: https://jsfiddle.net/fyf4nsk4/

Se quiseres [em vez de usar fade][1] podes fazer uma [transição com slide][2]. Tudo com CSS...


  [1]: https://jsfiddle.net/fyf4nsk4/1/
  [2]: https://jsfiddle.net/fyf4nsk4/2/