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/