Answer here will probably be application-specific, data-set specific. In any given situation you can try yourself, select $m$ (say, 5000) rows at random, do the same again, again, ... and compare results.
You could also exploit your situation to draw some hold-out sample, to use for independent model verification. If you are using some kind of automatic variable selection, that could be very valuable.
If you need confidence intervals for model parameters, those may be to long with this "use only a large random subsample" procedure, but, anyhow, the confidence intervals calculated with the full dataset are probably too short ... they depend on assumptions such as "the model is absolutely correct", "all variables measured without error", and so on, which might be fairly innocuous with small data sets, but not trustworthy with large data sets. Things like variables only measured with a finite (small) number of correct decimals will ultimately limit how short confidence intervals can be! You can yourself, with your data, investigate such questions by redoing the random subsampling many times, plotting the different coefficients obtained from each subsample, and compare the variation between them to the length of calculated confidence intervals.