(Abridged) Combining cosmic shear power spectra and cluster counts is powerful to improve cosmological parameter constraints and/or test inherent systematics. However they probe the same cosmic mass density field, if the two are drawn from the same survey region, and therefore the combination may be less powerful than first thought. We investigate the cross-covariance between the cosmic shear power spectra and the cluster counts based on the halo model approach, where the cross-covariance arises from the three-point correlations of the underlying mass density field. Fully taking into account the cross-covariance as well as non-Gaussian errors on the lensing power spectrum covariance, we find a significant cross-correlation between the lensing power spectrum signals at multipoles l~10^3 and the cluster counts containing halos with masses M>10^{14}Msun. Including the cross-covariance for the combined measurement degrades and in some cases improves the total signal-to-noise ratios up to plus or minus 20% relative to when the two are independent. For cosmological parameter determination, the cross-covariance has a smaller effect as a result of working in a multi-dimensional parameter space, implying that the two observables can be considered independent to a good approximation. We also discuss that cluster count experiments using lensing-selected mass peaks could be more complementary to cosmic shear tomography than mass-selected cluster counts of the corresponding mass threshold. Using lensing selected clusters with a realistic usable detection threshold (S/N~6 for a ground-based survey), the uncertainty on each dark energy parameter may be roughly halved by the combined experiments, relative to using the power spectra alone.