Explica o dicionário Houaiss (Lisboa, 2003) que mas vem (desabreviando as abreviaturas) do
português arcaico mais e, este, do latim magis; o valor adversativo originou-se do facto de, em muitos contextos em que se usava esta partícula, a ideia de adversativa estar implícita, do que resultou a fixação desse sentido na partícula
A palavra francesa mais (mas em português), vem também de magis, como seria de esperar. O Centre National de Ressources Textuelle et Lexicales explica que magis já havia assumido o valor de mas no latim (tradução minha):
Do sentido secundário [de magis] «de preferência, antes», nomeadamente nas construções non … sed magis [não … mas mais/antes], ac magis, magis autem […] veio o emprego adversativo (cf. primeiro na linguagem poética CÁTULO [84 – 54 a.C.], 68 30: id. … non est turpe magis miserum est [não é torpe, mais/antes miserável]; em prosa a partir de SALÚSTIO [86 – 34 a.C.], Jug., 96, 2: ab nullo repetere [sc. benficia] magis id laborare ut… [não pedia nada em troca [de favores], mas/antes fazia o que podia...]), os seus representantes românicos […] mostrando que magis tinha desde a época pré-românica assumido os empregos de sed (oposição forte) e de autem (oposição fraca);
Ainda segundo o Houaiss os primeiros registos conhecidos de mais, também grafado mays, quer no sentido de ‘mas’ quer do atual ‘mais’ são do século XIII. (Chegou-nos pouquíssimo material em português de séculos anteriores.) E encontramos imensos exemplos na poesia medieval do século XIII no Corpo Informático do Português Medieval. Também já se usava mas. O mais curioso é que mais ou mays aparecem na mesma cantiga, por vezes no mesmo verso, ora com um significado ora com outro. Eis alguns exemplos (ênfase minha; cada estrofe é de uma cantiga diferente):

Agora o que eu gostaria era de entrar na cabeça do pessoal do século XIII para saber se os dois sentidos de mais se lhe apresentavam completamente distintos (como os de porca para nós, o diabo da porca engoliu parafuso, porca e tudo) ou se mais como os de antes ou já, que nós empregamos com dois sentidos sem necessariamente nos darmos conta; ou, quando damos, detetamos uma ligação entre eles, como em:
Antes quero levantar-me mais cedo do que chegar ele antes de mim
Eles já chegaram. A Maria vem bem disposta; já o João vem com cara de poucos amigos