Recurrence networks are complex networks, constructed from time series data, having several practical applications. Though their properties when constructed with the threshold value \epsilon chosen at or just above the percolation threshold of the network are quite well understood, what happens as the threshold increases beyond the usual operational window is still not clear from a complex network perspective. The present Letter is focused mainly on the network properties at intermediate-to-large values of the recurrence threshold, for which no systematic study has been performed so far. We argue, with numerical support, that recurrence networks constructed from chaotic attractors with \epsilon equal to the usual recurrence threshold or slightly above cannot, in general, show small-world property. However, if the threshold is further increased, the recurrence network topology initially changes to a small-worldstructure and finally to that of a classical random graph as the threshold approaches the size of the strange attractor.