The Network-on-Chip (NoC) is an enabling technology to integrate large numbers of embedded cores on a single die. Traditional multi-core designs based on the NoC paradigm suffer from high latency and power dissipation as the system size scales up due to the inherent multi-hop nature of communication. The performance of NoC fabrics can be significantly enhanced by introducing long-range, low power, and high-bandwidth single-hop links between far apart cores. In this paper we present a design methodology and performance evaluation for a hierarchical small-world NoC with on-chip millimeter (mm)-wave wireless channels as long-range communication links. The proposed wireless NoC offers significantly better performance in terms of achievable bandwidth and energy dissipation compared to its conventional multi-hop non-hierarchical wired counterpart in both uniform and non-uniform traffic scenarios. The performance improvement is achieved through efficient data routing and an optimum placement of the wireless hubs and energy efficient transceiver design.