The cleanupOrphaned Performance section has wording that implies a document (or collection) scan:

cleanupOrphaned scans the documents in the shard to determine whether the documents belong to the shard. As such, running cleanupOrphaned can impact performance; however, performance will depend on the number of orphaned documents in the range.

However, cleanupOrphaned only makes sense with the context of the shard key so presumably uses the shard key index. The startingFromKey parameter defaults to minKey and is only valid if it matches the shard key pattern:

https://github.com/mongodb/mongo/blob/master/src/mongo/db/s/cleanup_orphaned_cmd.cpp#L97