Wie kann denn eine Armee zu Fuß und ohne große Ortskenntnis schneller sein als berittene ortskundige Soldaten?
Erhalten sie Hilfe von Einheimischen? Was anderes fällt mir da nicht ein. Vielleicht solltest Du Deine militärische Strategie näher ausarbeiten.
Ich würde eine Art Schwarmstrategie ausarbeiten. Es gibt vier zentrale Stellen, wo sich jeweils ca. 25% Deiner Armee aufhalten. Diese Stellen werden rund um die vermutete Position des Gegners gelegt. Dabei sind die vier Stellen nicht gleich weit voneinander entfernt, sondern immer zwei sind etwas näher aneinander dran, damit ein schnelles Unterstützen möglich ist. Zwischen den vier Stellen verkehren ständig Reiter, denn da der Feind wandert, muss Deine Armee mitwandern. Es geht also darum, ständig Informationen auszutauschen. Gleichzeitig sind die Meldereiter auch Späher. Ich würde die Frequenz so takten, dass ein Ausbleiben eines Meldereiters schnell auffällt und ein Hinweis sein kann, in welcher Richtung der Feind ist. Neben den Meldereitern gibt es richtige Späher, die von den vier Stellen aus sternförmig in alle Richtungen ausschwärmen und nach Spuren Ausschau halten und die ebenso getaktet sind, damit ein Ausbleiben ein Hinweis geben kann.
Das funktioniert nur mit vielen Reitern, aber Du hast ja genug und Unterstützung von mir.
Zu guter Letzt wird für das große Ganze auch geschaut, was überhaupt gangbare Wege sind. Ich kenne jetzt die Region um Wjelkow nicht. Ich stelle sie mir vor wie eine Landschaft in Schweden im Mittelalter. Wälder, Seen, Sümpfe, Wiesen. Die ersten drei sind nicht so gut passierbar. Es bietet sich für Freund und Feind an, leichte Pfade als Wegstrecken auszuwählen. Nutze das aus und postiere an wahrscheinlichen Pfaden Späher, die diese Wege versteckt im Blick behalten. Nimm dafür immer zwei Leute. Einer, der späht, der zweite, der im Erfolgsfall die Armee holt und weiß, wo der erste Späher sich versteckt hält. Der erste Späher bleibt vor Ort, verfolgt die Armee und gibt dann durch Äste oder Steine, Gekritzel im Boden (nur wenn es nicht regnet) oder ähnliches die Richtung der Bewegung an.
Um ganz sicher zu gehen, könnten die Meldereiter auch einen festen Satz an Passwörtern bekommen und/oder den Auftrag, bei drohender Gefangennahme sofort das Pferd zu töten. Damit Dir der Feind keine falschen Meldungen unterjubeln kann.
Damit solltest Du den Feind kriegen. Falls Deine Magier noch irgendwelchen Zauberkram machen können zwecks spähen, wäre das sicherlich auch hilfreich.
Das alles wie gesagt unter der Annahme, dass Du genug Militär vor Ort hast.