Tight upper bound for forming an $n$ element Red-Black Tree from scratch
To construct a red-black tree on $n$ elements you need to spend time $\Omega(n \log n)$, if you are only allowed to compare the elements' keys.
To see this notice that an in-order visit of any BST visits the nodes in increasing order of their keys.
If you were able to construct a red-black tree in time $t(n) = o(n \log n)$ then you'd also be able to sort $n$ elements in time $O(t(n) + n) = o(n \log n)$, contradicting the lower bound on sorting for comparison-based algorithms.
On the other hand, if the elements are already sorted then you can build a red-black-tree in time $O(n)$: just recursively build a balanced BST, if the last level is incomplete color its nodes as red, and color every other node black.
This requires linear time since the time complexity of the recursive algorithm can be described by the recurrence equation $T(n) = 2T(n/2) + O(1)$.