We report a measurement of the branching fraction Br(Bs -> Ds(*) Ds(*)) using a data sample corresponding to 1.3 fb^{-1} of integrated luminosity collected by the D0 experiment in 2002-2006 during Run II of the Fermilab Tevatron Collider. One Ds(*) meson was partially reconstructed in the decay Ds -> phi mu nu, and the other Ds(*) meson was identified using the decay Ds -> phi pi where no attempt was made to distinguish Ds and Ds* states. The resulting measurement is Br(Bs -> Ds(*) Ds(*)) = 0.039 +0.019 -0.017 (stat) +0.016 -0.015 (syst). This was subsequently used to estimate the width difference Delta Gamma^{CP}_s in the Bs-Bsbar system: Delta Gamma^{CP}_s / Gamma_s = 0.079 +0.038 -0.035 (stat) +0.031 -0.030 (syst).