The complexity of Vélu's formulas scales linearly with the size of the kernel subgroup, so directly applying them to a point of huge order is not feasible for isogenies of "cryptographic" degree.
Instead, SIDH implementations decompose an isogeny of degree $\ell^n$ into $n$ isogenies of degree $\ell$. An easy way to do this is the following:
Suppose given a point $P\in E$ of order $\ell^n$, where $\ell$ is "small"; we wish to compute $E/\langle P\rangle$.
We decompose the isogeny $\varphi\colon E\to E/\langle P\rangle$ as:
$$
E = E_0
\xrightarrow{\psi_1} E_1
\xrightarrow{\psi_2} E_2
\xrightarrow{\psi_3} \dots
\xrightarrow{\psi_{n-1}} E_{n-1}
\xrightarrow{\psi_n} E_n = E/\langle P\rangle
\text,
$$
where each $\psi_i$ has degree $\ell$.
A straightforward calculation shows that the kernels of the isogenies $\psi_i$ can be obtained by pushing $P$ through the previous isogenies $\psi_1\dots\psi_{i-1}$ and multiplying by an appropriate cofactor:
$$
\operatorname{ker}\psi_i = \langle[\ell^{n-i}](\psi_{i-1}\circ\dots\circ\psi_1)(P)\rangle
\text.
$$
Since $\lvert\operatorname{ker}\psi_i\rvert=\ell$ is small, computing each $\psi_i$ is efficient.
(Of course, this representation can also be used to efficiently evaluate $\varphi$ at a given point by simply passing the point through the chain of $\psi_i$s.)
Notice that it is this decomposition that gives the legitimate users of the system an advantage over attackers: It allows Alice and Bob to compute an isogeny in time logarithmic of the computational effort that an attacker needs to perform. In that sense, it is serves the same purpose as square-and-multiply (and its variants) for group-based Diffie-Hellman instantiations.
Finally, note that this straightforward strategy for computing $E/\langle P\rangle$ is not necessarily the most efficient possible: Depending on the relative costs of isogeny computations and point multiplications, there may be better strategies; see the original SIDH paper (Section 4.2.2) for details.
