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 singlepass 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. 

