I'm Brazilian myself, so I can tell you first-hand about the current situation. I'm fluent in both English and French, so I've also seen some foreign media outlets covering the situation here. We usually say that "Brazil is not for amateurs", which is meant to say that the case in our country is always complex, and care should be taken when forming opinions too quickly.
Given this preamble, I'll start actually answering your question:
"(...) and some have declared fears that Brazil's democracy may be under threat (...)"
A lot of care should be taken with this statement. Indeed since 2014 Brazilians are quite unhappy with the election process. In that election, blank and null votes outnumbered the elected president Dilma's votes (those blank/null happen because voting is mandatory in Brazil).
That being said, any claim by Bolsonaro himself (and not by his opposers or allies) that could be considered an aggression to democracy is at least 10 years old. He does however soft-tone the military regime that held power in Brazil before our current republic, which sounds pretty bad, but is not a statement in favor of a new military regime.
There is also a big concern over the ballot casting machines and their safety, which was already present in 2014 (when Bolsonaro didn't run for presidency).
“banish the marginal reds [delinquents of the left] from the fatherland; they will leave or be imprisoned,” he threatened, in a “cleansing never seen before in this country.”
Time will tell how much of this is rhetoric and how much he intends to carry out (...)
This is rhetoric but will likely be carried out. Most people voting for Bolsonaro are not his fans, but rather detractors from PT (the worker's party), which was involved in major corruption scandals. Ever since I was born, I've always heard that the vast majority of politicians in Brazil are corrupt, and many important people from PT are in jail and/or responding to a high number of lawsuits. This includes the candidate PT tried to enroll for election (Lula, who is in jail), and Fernando Haddad who answers for having parts of his campaign spending illegally paid by a private company. These people will indeed be prosecuted (and many convicted) but by the judicial branch, not by the president.
The fear in place had PT won the election would have been some kind of presidential pardon for PT's crimes (particularly Lula's) and rearrangements in the police and public prosecutors force, which would have caused investigations over corruption scandals to halt. In the end, Bolsonaro can fulfill his rhetoric by doing nothing. Though most of the population expects him to reinforce investigation and support judicial power. He is expected to nominate the judge who convicted Lula for the Supreme Court.
But how powerful is the Brazilian Presidency?
By itself, not that powerful. But with the help of Congress, quite a lot. Bolsonaro indeed does not hold majority of Congress, but presidents in Brazil are as effective as their skill to deal with Congress and Senate. Lula bought Congress with corruption money. Temer did so with office chairs and "emendas parlamentares" (which basically means freeing money to a congressman's proposal).
so I would expect forming a majority coalition would require watering down anything radical.
Those who actually fear he will abuse his power are those concerned about his links to the military. There are people in Brazil today who even support military intervention (a completely absurd proposal for any reasonable person).
He may, however, be able to form majority to approve right-wing projects and decisions, which for the left-wingers is in itself radical and unwanted.
The press seem to focus on how Bolsonaro doesn't seem to like democracy or rule of law much, but regardless of his views, what can he legally do?
Again: not much, but quite a lot. It depends on who you ask. Owning guns has been basically forbidden in Brazil, but he can at a stroke of his pen revoke this status. He can also strongly facilitate the possibilities for carrying guns in public.
Most of the fearsome things would require major support from Congress and Senate, but note that one of his sons was the most voted senator and another was the most voted deputy. If he manages to have his children as chiefs of both legislative chambers over the next year, he can do a lot more while remaining protected.
