In -20 °C weather, creeks below waterfalls here form ice columns. What are these called? Ice-canoes?
These are classed as ice spikes. You are correct in noting the occurrence downstream of waterfalls, as this extra turbulence is part of the formation process. The USGS page here has information on the formations, photographs and a list of criteria involved in their formation:


  The winter conditions at each of the ice formation’s locations were
  similar:
  
  
  Freezing or sub-zero temperatures and low flow in channel during    winter months
  Ice covered the surface of the stream and accumulated at depths long    the banks restricting flow
  In each instance, water flowed over a structure such as a weir or    beaver dam causing turbulence in the flow
  Due to the turbulence and restriction in flow, water emerged from    small surface openings downstream of the structure and began to
  freeze – probably rapidly in some cases due to the sub-zero
  temperatures at times
  Whether the freezing water resulted in a “columnar” or a “frothy,    bubble” ice structure depended on the unique conditions at each
  location and the weather conditions over time