Those leading figures you ask about are the Eastings and Northings of the SW corner of the "medium" square "U" which is inside its parent large square "S".
Each large square is 500km wide, as you state.
Each large square is further subdivided into 25 "medium" squares, 100km wide.
I call them medium squares because they too, as you know, are subdivided further into 100 x 100 topographic map, small grid squares, 1km wide. (Actually, there's yet another intermediate level of squares, 10km wide, between "medium" and "small"!)
Now, the labeling pattern is the same for both large and medium squares (i.e., the A, B,C ... X, Y, Z pattern also exists inside each large square), so each medium square has a unique two letter label -- one for its parent, one for itself.
The origin of the UK grid (i.e., 000000,000000), is at the very SW corner of the large square "S".
Thus the 6-figure reference for the origin is SV000000. The "V" means it is in the SW corner of its parent, "S".
The following index map is from Using the National Grid, a two-page consumer guide. I added two red dots for the sample locations that follow.
The Southampton reference of SU418122 is equivalent to 441800,112200 because the SW corner of medium square "U", is 4 squares (or 4 x 100km) east and 1 square (or 100km) north of its parent large square's SW corner.
Another example: my home town of Leigh-on-Sea, on the North of the Thames estuary, is at TQ845858. This means its
- Easting is T + Q + 845 = 1 x 500km (T is 1 large square east of S) + 0 x 100km (Q is 0 medium squares east of its parent's origin) + 845 x 100m = 584500m
- Northing is T + Q + 858 = 0 x 500km (T is 0 large square north of S) + 1 x 100km (Q is 1 medium squares north of its parent's origin) + 858 x 100m = 185800m
The combined graticule and grid in the map below is from A guide to coordinate systems in Great Britain
, a good 43-page technical document.
Notice the relationship between the "false origin", the "true origin", and the SW corner of the ref. square SU. (It should explain the honest confusion in Brad's answer.)