Direct conversion from regular expression to MSO
The direction from regular expressions to MSO is easy, as MSO is versatile. For a regular expressions $R$ let us construct formulae $\varphi_R$.

$\varphi_{\emptyset} := \bot$

$\varphi_{\varepsilon} := \forall x\bot$

$\varphi_a := \exists x(P_a x \wedge \forall y(x=y))$

$\varphi_{R_1 | R_2} := \varphi_{R_1} \vee \varphi_{R_2}$. 

$\varphi_{R_1R_2} := \exists X(\forall y\forall z((Xy \wedge \neg Xz)\to y&lt;z) \wedge [\varphi_{R_1}]_{Xx} \wedge [\varphi_{R_2}]_{\neg Xx})$

$\varphi_{R*} := \exists X(\forall y\forall z((\forall x((\neg x&lt;y \wedge \neg z&lt;x)\to(Xx\leftrightarrow Xy))) \wedge \forall x((x&lt;y\wedge(Xx\leftrightarrow Xy))\to\exists x'(x&lt;x'\wedge x'&lt;y\wedge\neg(Xx'\leftrightarrow Xy))) \wedge \forall x((z&lt;x\wedge(Xx\leftrightarrow Xy))\to\exists x'(z&lt;x'\wedge x'&lt;x\wedge\neg(Xx'\leftrightarrow Xy)))) \to [\varphi_R]_{\neg x&lt;y \wedge \neg z&lt;x})$

Here, $[\varphi]_{\psi(x)}$ denotes the relativization of the formula $\varphi$ to the formula $\psi$. 

As you can see, the translation is linear.

In the other direction, I suggest to transform MSO to regular expressions in two steps, with NFAs in between. I know this is not what you are asking for. For complexity analysis it should suffice, however: The translation from MSO to NFAs is known not to have any elementary lower bound. And a direct translation to regular expressions cannot be any better, because of the linear translation from regular expressions to NFAs.