I guess the layout performance really depends on the layout algorithm implementation - our Sugiyama layout works ok with about 500 links or less but it's really slow with 1000 link and more (the number of nodes doesn't really matter - the layout works ok with 4000 nodes and 500 links).
I'd like to ask you for some more information about your specific case so that we could help you better.
I've attached the sample project I used for testing so you could examine it.
We're looking forward to hearing from you.
the Telerik team