As far as I know the range of squares explored in each WU is always the same (10 millions for the new R10 WUs?) so... what exactly makes each WU run time to be different?

Because its not 10 million squares for every WU, it is 1 billion (1% of 1 billion = 10 million) squares for each WU. However, as Hoarfrost stated, that 10 million/1 billion value is a rough estimate. So it could easily be 8 million for every 1% progress on the WU, but could also be 14 million for every 1% progress on said WU.

And that's exactly why I made this thread, to understand why it is an estimate. As far as I know, each WU grabs some squares (let's say 1 billion) and compares them, looking for those that are ODLS pairs, how can their number being unknown? Is a specific reason for that?

Diagonal Latin Squares are a bit like sudoku - every square must have unique values in rows, columns and diagonals. Workunit file provides square with values in 1st row, both diagonals and some from 2nd/3rd rows. All other square cells are filled by app. It is unknown how many squares can be generated from given initial partially filled square, hence an estimate has to be used.

---

Thank you for your answer, I had no idea about that part! Now that explains everything!