13 bags with 13 coins each

Did he guess? - No
How did he know? - Since Scrooge told him that if he told him the number of coins, he could tell him how many bags/coins per bag there were, we know it's a square (because otherwise you could flip the bags and coins per bag and not know for sure). It also needs to be a prime number so that the only factors are 1, the unsquared factor and the squared factor. The only number that fits is 169 (factors 1, 13, and 169). Both 1 and 169 get ruled out by Scrooge's other rules leaving 13x13.