Does this sentence sound grammatically correct?
He used lots of paper and cut them into different sizes.
Or should I use it instead?
This is a case where what is actually being talked about is multiple, but we are using a word that takes singular forms ("paper" is uncountable, but it takes a singular pronoun). The singular is technically correct, but there's some leeway to use the plural. BrE has more of a tendency to use the plural in these cases. You can also say "He used several pieces of paper and cut them into different sizes." There, "them" refers to "pieces", so there isn't question that it's plural.
If you have a countable noun, you can say (for example) a lot of things or (less formally) lots of things. Whichever you say, the pronoun is then they.
If you have a mass noun, you can say a lot of paper or (less formally) lots of papers. Whichever you say, the pronoun is then it.
("Paper" can also be countable in some cases, but that's irrelevant to this point.)
The pronoun depends on the number of the noun being quantified ("paper" or "things"), not the quantifier "lot"/"lots".
The same is true of "few". If you refer to "a few things", the following pronoun will be "they", not "it".
Note: The following note appears under "lot" at Lexico.com:
The expressions a lot of and lots of are used before nouns to mean ‘a large number or amount of’. In common with other words denoting quantities, lot itself does not normally function as a head noun, meaning that it does not itself determine whether the following verb is singular or plural. Thus, although lot is singular in a lot of people, the verb that follows is not singular. ( https://www.lexico.com/definition/lot )
In the same way that these quantifiers don't determine the number of the following verb, they don't determine the number of the following pronoun, either.
It appears on first reading that "lots of paper" should be understood as a plural noun (lots) modified by an of-genitive "of paper". However a better analysis would be that "lots of" is a determanitive phrase, with a similar function to "some" (similar function but different meaning)
So consider
He used some paper and cut it into different sizes.
It is clear here that "it" refers to "some paper" which is grammatically singular.
Similarly you should use "it" to refer to "lots of paper", as the agreement is with the singular "paper" and not the plural "lots".
[Note that in rare cases "lots of" might actually refer to the plural of "lot". "He divided his field into 15 lot of land, and sold them at auction." That is rare, and you would probably rephrase to avoid the difficulty]
It would also be correct to say:
He used lots of sheets of paper, and cut them into pieces
Here the word "them" refers to "sheets of paper", which is grammatically plural.
So "lots of paper" is parsed as [lots of] [paper] and is singular. But "sheets of paper" is parsed as [sheets] [of paper] and is plural.