Fast computation of Frobenius norm under memory limits
Some of the results depend on the model under which the matrix is presented, but there's a large collection of results that use sampling or sketching techniques to estimate norms accurately. Among some of the key results are:


sketching methods based on the use of 2-stable distributions: these work even if the entries are "streamed in" in some order, and also work if you are presented instead with the A and the B entries. 
column sampling methods.


Again, it would be unfair to single out a single paper, also because it's not exactly clear which model you're working in: best to google 'norm estimation' or 'column sampling' to find some of the related results. This survey by Mahoney is a useful reference for sampling methods.