Тут важно отметить вот что: они не преодолели бы Стену ВООБЩЕ никак, если бы не была разрушена магическая защита Стены. То есть до всей этой истории с Браном, ни по верху, ни по низу, ни сквозь - не могли пройти. Спасибо Детям леса. Ну и плавать не умеют, значит путь по воде тоже закрыт.
Вероятнее всего, ходоки просто ждали начала зимы. В заставке первой серии 7-го сезона восточнее стены вода показана замерзшей. По ней можно было пройти, видимо, и ходоки со своей армией двигались как раз к Восточному дозору, чтобы это сделать, обогнуть Стену. Ну и ходоки, ко всему прочему, еще и меняют климат там, где находятся. Да и Пес видел в огне примерно это же.
Дракон просто очень удачно вступил с ними в бой и пополнил их войско, пусть они и знали об их рождении.