Media reports don't always tell the full story, and don't always tell the story accurately. It's useful to look at the actual research paper. In this case, it's in Nature Communications and therefore open access (no subscription needed).

The paper is: Jonas Gregorio de Souza et al., Pre-Columbian earth-builders settled along the entire southern rim of the Amazon, Nature Communications 9, 1125 (2018), http://dx.doi.org/10.1038/s41467-018-03510-7

Note that the estimate of 1 million inhabitants is for an area of 400,000 km^2, for a population density of 2.5 persons/km^2. For context, this is approximately the population density of the Scandinavian Peninsula, Finland, and Russia in 1300, and about 1/10 the population density of much of Western Europe in 1300. This is not a high population density. It does mean that the area was populated by farmers rather than bands of nomadic hunter-gatherers.

How come the Portuguese did not find them when arriving in Brazil?

It looks like they did. From the paper:

That the UTB [Upper Tapajós Basin] hid settlements comparable to those found to the east and west was suggested by 18th century accounts, where the region was portrayed as densely populated, with large villages connected by straight and wide roads.

citing Pires de Campos, A. Breve notícia que dá o capitão Antônio Pires de Campos do gentio que há na derrota da viagem das minas do Cuyabá e seu recôncavo. Rev. Trimest. do Inst. Histótico, Geográfico, e Etnográfico do Bras. 5, 437-449 (1862) for those 18th century accounts.

These villages weren't giant lost cities. They were villages. The estimate of 1,000,000 for the population is for the entire area, not for the 81 villages/towns (they estimate 1300 or more such villages for the whole area). The largest of the sites in the study had an estimated population of 2594 (see the supplementary information accompanying the paper; Supplementary Table 4 lists the sites and estimated populations); most had estimated populations well under 1,000, and the smaller ones under 100.

The above doesn't mean that the work reported in this paper is insignificant. The estimate of 1,000,000 people living in this area of 400,000 km^2 is the same as the low-end estimates for the pre-Columbian population of all of Amazonia, and lends credence to the high-end estimates in excess of 10,000,000 (for all Amazonia).

One thing that is not always clear from the media reports of work like this is the earlier work on the topic. The work discussed above isn't a sudden new relevation - it's another contribution to an ongoing body of work. For example, Clement CR, et al. The domestication of Amazonia before European conquest. Proc. R. Soc. B 282: 20150813 (2015), http://dx.doi.org/10.1098/rspb.2015.0813 discusses Amazonian agriculture and the pre-Columbian population (suggesting a minimum of 8-10 million). The modern work on this goes back to the last millenium, e.g., Wüst, I., & Barreto, C. (1999). The Ring Villages of Central Brazil: A Challenge for Amazonian Archaeology. Latin American Antiquity, 10(1), 3-23, https://doi.org/10.2307/972208

Where did they go?

Almost certainly, disease played a major role.

How come the Portuguese did not find them when arriving in Brazil?

If you'd like to read the early colonial accounts of the various Amazonian communities, I'd recommend checking out Orellana's entrada, which was the first major expedition by Europeans through the Amazon. Orellana began in the Andes and traveled downriver to the Atlantic. Buddy Levy's River of Darkness is a good summation Orellana's expedition along with some archaeological context.

For the cliffnotes version, you may want to see my older post on a related topic.