Here is a try: Fix $s \leq t$, then
\begin{align*} M_t &= \max \left\{ \sup_{r \leq s} B_r, \sup_{s < r \leq t} B_r \right\} \\ &= \max \left\{M_s, \sup_{r \leq t-s} (B_{r+s}-B_s)+B_s \right\}. \end{align*}
The restarted process $W_r := B_{s+r}-B_s$, $r \geq 0$, is again a Brownian motion. If we denote by $M_t^W := \sup_{r \leq t} W_r$ its running maximum, then we see that
$$M_t = \max\{M_s,M_{t-s}^W+B_s\}.$$
Since $(W_t)_{t \geq 0}$ is independent from $\mathcal{F}_s$, we find that
$$\mathbb{E}(M_t \mid \mathcal{F}_s) = g(M_s,B_s),\tag{1}$$
where
$$g(x,y) := \mathbb{E}( \max\{x,y+M_{t-s}^W\}).$$
The aim is to show that the function $g(M_s,B_s)$ cannot be measurable with respect to $\sigma(M_s)$ (intuivitely this is clear, but making it rigorous is not so easy). If we manage to show this, then it follows from $(1)$ that $(M_t)_{t \geq 0}$ is not Markovian (...because if it were Markovian then the left-hand side of $(1)$ would be $\sigma(M_s)$-measurable).
First we need to get our hands on $g$. To this end, we use the reflection principle. By definition,
$$g(x,y) = x \mathbb{P}(x>y+M_{t-s}^W) + \mathbb{E}((y+M_{t-s}^W) 1_{y+M_{t-s}^W \geq x}).$$
Using the fact that $M_{t-s}^W$ equals in distribution $|W_{t-s}|$, we see that
$$\mathbb{P}(x>y+M_{t-s}^W) = \mathbb{P}(|W_{t-s}| < x-y)$$
and
\begin{align*} \mathbb{E}(M_{t-s}^W 1_{y+M_{t-s}^W \geq x}) &= \mathbb{E}(|W_{t-s}| 1_{|W_{t-s}| \geq x-y}) \\ &= \sqrt{\frac{2}{\pi(t-s)}} \int_{x-y}^{\infty}z \exp \left(- \frac{z^2}{2(t-s)} \right) \, dz \\ &= \sqrt{\frac{2(t-s)}{\pi}} \exp \left(- \frac{(x-y)^2}{2(t-s)} \right). \end{align*}
Consequently,
\begin{align*} g(x,y) &= x \mathbb{P}(|W_{t-s}|<x-y) + y \mathbb{P}(|W_{t-s}| \geq x-y) + \sqrt{\frac{2(t-s)}{\pi}} \exp \left(- \frac{(x-y)^2}{2(t-s)} \right). \end{align*}
Writing $$ \mathbb{P}(|W_{t-s}|<x-y) = 1- \mathbb{P}(|W_{t-s}|\geq x-y)$$ we see that $$g(x,y) = x+h(x-y) \tag{2}$$ for some continuous function $h$. More precisely, $$h(r) := - r \mathbb{P}(|W_{t-s}| \geq r) + \sqrt{\frac{2(t-s)}{\pi}} \exp \left(- \frac{r^2}{2(t-s)} \right), \qquad r \geq 0.$$
Pick disjoint intervals $[a,b]$ and $[c,d]$ such that $h^{-1}([a,b])$ and $h^{-1}([c,d])$ have positive Lebesgue measure.
Finally, we are ready to check that $g(M_s,B_s)$ cannot be $\sigma(M_s)$-measurable. Suppose, to the contrary, that it were $\sigma(M_s)$-measurable. Then it is immediate from $(2) $that $h(M_s-B_s)$ is also $\sigma(M_s)$-measurable. Consequently, there would be a Borel set, say $A$, such that
$$\{h(M_s-B_s) \in [a,b]\} = \{M_s \in A\}. \tag{3}$$
Since $M_s-B_s$ has a strictly positive density on $(0,\infty)$, we have, by our choice of $[a,b]$,
$$\mathbb{P}(M_s \in A)>0,$$
and so $A$ has strictly positive Lebesgue measure. Moreover, the fact that $(M_s,B_s)$ has a strictly positive density (on its support) implies that $(M_s,M_s-B_s)$ has a strictly positive density (on its support). Since $A$ and $h^{-1}([c,d])$ have positive Lebesgue measure, we obtain that
$$0 < \mathbb{P}(M_s \in A, M_s-B_s \in h^{-1}([c,d])) = \mathbb{P}(M_s \in A,h(M_s-B_s) \in [c,d]). \tag{4}$$
On the other hand, $(3)$ and the disjointness of the intervals $[a,b]$ and $[c,d]$ shows that
$$\mathbb{P}(M_s \in A,h(M_s-B_s) \in [c,d]) = \mathbb{P}(h(M_s-B_s) \in [a,b], h(M_s-B_s) \in [c,d])=0,$$
which contradicts $(4)$.
Remark: Using a reasoning very similar to that at the beginning of this answer, it is possible to show that the two-dimensional process $(M_t,B_t)_{t \geq 0}$ is Markovian. By the way, also $M_t-B_t$ is Markovian.
