I would presently say no. It is not redundant. Consider just what the word redundant means:

1. Superfluous; exceeding what is necessary.
2. (of words, writing, etc) Repetitive or needlessly wordy.
3. (chiefly Britain, New Zealand, Australia) Dismissed from employment because no longer needed; as in "rendered redundant".
4. Duplicating or able to duplicate the function of another component of a system, providing back-up in the event the other component fails.^[1]

Given these definitions, it seems to me that you would effectively need to mean the same thing twice at least twice in order to be redundant, unnecessarily. That is unless you pay the words you employ wages. However, in this sentence, you mean two very different things.

The word many is being used as a quantifier² to modify a noun, and the appropriate one to modify a pluralized, and hence count noun. It specifies you mean a higher number of that noun rather than a lower number of them.

1. many Being or consisting of a large number of units or individuals; numerous: often used alone, the noun being understood. ^[3]

Although millions of can be used in a tropical sense to mean many, that is not what is happening here. You are using it in the very much more literal sense of the number you get if you multiply a thousand by another thousand.

MILLION, noun mil'yun. [Latin mille, a thousand.]

1. The number of ten hundred thousand, or a thousand thousand. It is used as a noun or an adjective; as a million of men, or a million men. As a noun, it has a regular plural, millions.

2. In common usage, a very great number, indefinitely. ^[4]

Given that a number can be considered type of unit⁵, it seems to fit well with the already provided definition of the word many.

If you do not add the grammatical quantifier, the reader is free to make their own assertions, and might assume you only traveled a few million miles. Consider this quotation from as demonstrating such an opposite is a possibility: "Which only shows how small the vastest of human catastrophes may seem, at a distance of a few million miles." — Tales of Space and Time by H. G. Wells

As such, the many is necessary unless you want the sentence to possibly mean something else, and thus, is not redundant.

Moreover, it only seems natural if you can apply a modifier needfully, its antonym would be able to do the same. As a matter of fact, a context very similar to the one you have specified is exemplified here:

In one way, we can see many trillions of miles, but, as we should expect, not very clearly. We can see the sun, and he is more than ninety millions of miles distant. Thus, when we gaze at him, we are seeing many millions of miles.^[6]

My main reservation is just how many qualifies as many, and just how few qualifies as a few, but that's already the subject of a different question.

¹ The wikitionary definitions from their Redundant entry, which is licensed under the CC-BY-SA 3.0 license
² See: The Farlex Book of Grammar's section on determiners.
³ The Century Dictionary and Cyclopedia s.v. Many^1
4 The American Heritage Dictionary of the English Language by Noah Webster's definition of Million.
⁵ See: The American Dictionary of the English Language's definition of number
⁶ Seeing A Trillion Miles from Volume 92 of Popular Science Monthly in 1918 (I.S.S.N. 0161-7370)