How far below zero it needs to be is not the most important factor here
The real important factors are the dimensions of your river, how slowly it freezes, how fast the water is moving, and how far your drop is.
Waterfalls do not just suddenly freeze in place, instead the surface of the river freezes creating a surface for the liquid water underneath to cling to as it flows under it and itself subsequently freezes. A wider, faster moving waterfall is harder to freeze because you must first freeze the entire top edge of the waterfall in a fashion that creates an ice bridge to build on. This makes narrower waterfalls more ideal. If you have a wider river, you will want many rocky outcroppings at the waterfall's edge so that you have several shorter ice bridges instead of one longer one. Otherwise your river will have more time to freeze depriving you of the needed flow before you can start building your actual icy waterfall.
Once you have a solid icebridge over flowing water, you get icicles that slowly form. The slower your water freezes the better because once the river freezes through you will eventually stop having flowing water to continue to build the ice up. A slower starting water flow is also better because if the water is flowing too quickly with too much volume, then it will melt the ice faster than the cold air can build it up.
As the icicles grow they will also become heavier increasing their odds of breaking and falling off under their own weight, ideally the temperature will continue to slowly drop as the icicles form strengthening the ice at the top so it does not snap will allowing enough water to keep flowing to continue to build the ice up. The longest icicles in recorded history were ~27 feet long; so, that is probably about the limit of how high an ice waterfall can be... however, if you have a multi-stepped waterfall, you may get a much larger ice-face from ice bridges forming at multiple points in your decent.
Is Your Waterfall Doable?
In short, yes but it is much harder if your waterfall is not shaped right or if it is moving too fast. In the examples below, the first waterfall has a lot more shelves and narrow areas to bridge making it easier to freeze. The second one would probably not freeze except under extraordinary conditions.

Speaking of extraordinary conditions, Starfish Prime's Niagara falls example demonstrates, several really good points about this process that I think deserves a little bit of extra attention. If you look at section (A) below you will see where an ice bridge formed and the waterfall is just stepped enough to get the multiple layers of icicles. Section (B) shows another mechanic by which larger faster flowing waterfalls can freeze where by the water at the bottom freezes and builds up. It is more structurally sound than hanging ice but typically requires lower temperatures because you need to contend with the depth of the water at the waterfall's base. It also tends to look more like piled up clumps of snow and ice and less like a "frozen waterfall"; so, it probably does not answer your question as well, but I suppose it can help compensate for a bigger more overhanging waterfall if it builds up high enough.

As for your related questions:
The main river does not need to be completely frozen for this to happen, but there will at the very least be patches of ice, probably along the shores and shallows. The middle, deeper parts of the river will take longer to freeze, but if you want the icefall to be around for awhile, it will need to stay cold enough that the river will eventually fully freeze.
In the event of a long term, full freeze, they can just melt ice and snow for water. Should not be a big deal.
If the ice is thick enough, yes you could use sledges to traverse it, but it has to get and stay pretty cold for a long time for the ice to get thick enough for this to be a good idea. The icefall would probably need to form at the beginning of a freeze, and they would need to wait days or weeks for the river to harden enough to support traffic.