Dark matter which is bound in the Galactic halo might self-annihilate and produce a flux of stable final state particles, e.g. high energy neutrinos. These neutrinos can be detected with IceCube, a cubic-kilometer sized Cherenkov detector. Given IceCubes large field of view, a characteristic anisotropy of the additional neutrino flux is expected. In this paper we describe a multipole method to search for such a large-scale anisotropy in IceCube data. This method uses the expansion coefficients of a multipole expansion of neutrino arrival directions and incorporates signal-specific weights for each expansion coefficient. We apply the technique to a high-purity muon neutrino sample from the Northern Hemisphere. The final result is compatible with the null-hypothesis. As no signal was observed, we present limits on the self-annihilation cross-section averaged over the relative velocity distribution $<sigma v>$ down to $1.9cdot 10^{-23},mathrm{cm}^3mathrm{s}^{-1}$ for a dark matter particle mass of $700,mathrm{GeV}$ to $1000,mathrm{GeV}$ and direct annihilation into $ ubar{ u}$. The resulting exclusion limits come close to exclusion limits from $gamma$-ray experiments, that focus on the outer Galactic halo, for high dark matter masses of a few TeV and hard annihilation channels.