You can scale your matrix by, say, the inverse of the largest/smallest(nonzero) entry before you compute the norm and use that $\|aM\|=|a|\|M\|$.
And have a look into Higham's book Accuracy and Stability of Numerical AlgorrithmsAlgorithms to understand how these scalings have an effect on the accuracy.