The analysis of seismic wave propagation and amplification in complex geological structures raises the need for efficient and accurate numerical methods. The solution of the elastodynamic equations using traditional boundary element methods (BEMs) is greatly hindered by the fully-populated nature of the matrix equations arising from the discretization. In a previous study limited to homogeneous media, the present authors have established that the Fast Multipole (FM) method reduces the complexity of a 3-D elastodynamic BEM to $N \log N$ per GMRES iteration and demonstrated its effectiveness on 3-D canyon configurations. In this article, the frequency-domain FM-BEM methodology is extented to 3-D elastic wave propagation in piecewise-homogeneous domains in the form of a FM-accelerated multi-region BE-BE coupling approach. This new method considerably enhances the capability of the BEM for studying the propagation of seismic waves in 3-D alluvial basins of arbitrary geometry embedded in semi-infinite media. Several fully 3-D examples (oblique SV-waves) representative of such configurations validate and demonstrate the capabilities of the multi-domain fast multipole approach. They include comparisons with available (low-frequency) results for various types of incident wavefields, and time-domain results obtained by means of Fourier synthesis.