Million-selling records go back to the early 1900s, but it's impossible to know which one was first, because sales weren't tracked like they are now.  Caruso's "Vesti La Giubba" [Victor] is listed 1st in _Million Selling Records from the 1900s to the 1980s_ by Joseph Murrells (Arco 1984), but he includes 3 versions from 1903-1907, saying only that the 1907 version made up the bulk of sales.  Another book said that the 1907 version sold "hundred of thousands" of copies.  I see it listed on the internet as the first, but never citing where that information comes from.

The next four songs in Murrell's _Million Selling Records_ are:

2)  "The Preacher and the Bear" by Arthur Collins (1905) [victor]

3) "Laughing Song" by Burt Shepard (1910) [Gramophone Co. - UK] - "It was particularly popular in the Oriental countries such as India, and is estimated to have sold over a million in that part of the world alone."

4) "Ragging the Baby to Sleep" by Al Jolson (1912) [Victor]

5) "The Spaniard That Blighted My Life" by Al Jolson (1913) [Victor] - "sales were reported of 1,846,000.