According to Devel::Peek, it's an array rather than a linked list. That doesn't change the complexity, though.

To delete weak ref #X:
O(X) to locate + O(N-X) to delete
= O(N) total

Best, average and worse case to delete one weak ref of N is O(N).

To delete all N weak refs:
O(N) + O(N-1) + O(N-2) + ... + O(1)
= O(N**2)

Best, average and worse case to delete all N weak refs is O(N**2).

A hash, on the other hand, would scale much better.

Best, average and worse case to delete one weak ref of N is O(1).
Best, average and worse case to delete all N weak refs is O(N).

Update: Added analysis for hash.