What is the best algorithm for computing covariance that would be accurate for a large number of values like 100,000 or more?
Check out How to calculate correlation accurately. There are two common formulas that are algebraically equivalent but one has much better numerical properties than the other.
The single-pass and parallel versions at Wikipedia may be what you're looking for. The single pass version is more numerically stable, but moves a division into the inner loop, which may hurt performance.
A single pass stable algorithm has been discovered in the time since this question has been originally answered:
Bennett, Janine, et al. "Numerically stable, single-pass, parallel statistics algorithms." Cluster Computing and Workshops, 2009. CLUSTER'09. IEEE International Conference on. IEEE, 2009.
An implementation is given in Boost.