You need a loop to get a large number of messages. You can use the -PageSize parameter together with the -Page parameter. Increment the -Page value by one after each Get-QuarantineMessage and repeat the query as long as the number of message in the page is greater than zero.
With a PageSize of 1000 and a Page starting at one and going up to 1000 you should be able to retrieve 1,000,000 messages.
A more complete explanation of doing this can be found here: https://www.powershellgeek.com/2023/02/03/powershell-paging-in-microsoft-365/#:~:text=With%20this%20code%2C%20the%20Get-QuarantineMessage%20cmdlet%20will%20list,pick%20a%20particular%20message%20from%20a%20particular%20page.