While discussing this question, it is assumed that intercession {shafa‘ah} exclusively rests with God as it is stated in the Holy Qur’an:

"قل لله الشفعة جميعاً."

“Say, ‘All intercession rests with Allah’.”1
Therefore, turning for intercession to any other than God means asking for God’s absolute right from His servant and seeking such a need is, in reality, worshipping other than God which is inconsistent with “monotheism in worship” {tawhid fi’l ‘ibadah}.
Reply: Here, shirk {polytheism} does not mean polytheism in essence, creative power or in design (governing); it actually means polytheism in worshipping Him.
Obviously, elucidating this point depends on the correct interpretation of worship and devotion, and we all know that in interpreting the word “worship” we have not been authorized to consider as “worship” any form of submission to a creator or any type of request from a servant (of God).
According to the Glorious Qur’an, the angels prostrated to Adam (Adam) (‘a):

﴿ فَإِذَا سَوَّيْتُهُ وَنَفَخْتُ فِيهِ مِن رُّوحِي فَقَعُوا لَهُ سَاجِدِينَ ٭ فَسَجَدَ الْمَلَائِكَةُ كُلُّهُمْ أَجْمَعُونَ ﴾

“‘So when I have proportioned him and breathed into him of My spirit, then fall down in prostration before him.’ Thereat the angels prostrated all of them together.”2
This prostration, though decreed by God, it was not meant to worship Adam (‘a), otherwise God would not have ordered it.
Similarly, the sons of Ya‘qub (Jacob) (‘a) as well as Ya‘qub himself prostrated before Yusuf (Joseph) (‘a):

ورفع أبويه على العرش وخرُّوا له سجداً.

“And he seated his parents high upon the throne, and they fell down prostrate before him.”3
If we consider this humility as equivalent to worshipping Yusuf (‘a), then Prophet Ya‘qub (‘a) who has a station of infallibility {‘ismah} must not have done it nor must he have been pleased with his sons’ act. Meanwhile, there is no way of expressing humility that is loftier than prostration.
Consequently, we must distinguish between the concept of “humility” or “asking from other than God” and that of “worshipping God”. The true meaning of worship is to think of a creature as a god and worship it/him, or to regard a phenomenon as one of God’s creatures and assume that it has been commissioned to perform divine actions, such as governing the world and forgiving sins.
But when showing humility to someone and we do not regard that one as a god and we do not think that he or she has been commissioned to perform divine actions, such humility will mean nothing but an expression of respect to that one as in the case of the angels’ reverence to Adam (‘a) or the honor paid by the sons of Ya‘qub to Yusuf (‘a).
Regarding this question, it must also be stated that to assume that the right of intercession has been granted to the rightful intercessors and that they can unconditionally intercede for people or forgive their sins will entail polytheism {shirk}, for this means seeking what is with God from other than Him.
But when we think that a group of pure servants of God are authorized within a certain context to intercede on behalf of the sinners without assuming that they possess the station of shafa‘ah and we think that the most important requisite is God’s permission and good pleasure, it is clear that resorting to a righteous servant (of God) for intercession does not mean recognizing him as a god nor does it mean that the responsibility of the divine affairs has been entrusted to him; rather, it means asking someone who is worthy of it.
In the lifetime of the Prophet (S) sinners would come to him and ask him for forgiveness (of the sins) and he would not accuse them of polytheism. In the Sunan of Ibn Majah, the Prophet (S) is reported to have said:

"أتدرون ما خيّرني ربي الليلة؟ قلنا: الله ورسوله أعلم. قال: فإنه خيّرني بين أن يدخل نصف امتي والجنة
وبين الشفاعة فاخترت الشفاعة قلنا يا رسول الله أدعُ الله أن يجعلنا من أهلها قال هى لكل مسلم."

Do you know what God has granted me this night?” We said: “God and His Prophet know better.” He added: “He has granted me the favor of choosing one of two things: the first is that half of my ummah shall enter paradise and the second is the authority to intercede. So I chose the second.” We said: “O Messenger of Allah! Ask God that we will be worthy of it (intercession).” He said: “It will be for all Muslims.4
In this hadith, it is clearly shown that the Companions of the Prophet (S) are asking him for intercession, saying, “Ask God that…”
The Holy Qur’an also states:

﴿ وَلَوْ أَنَّهُمْ إِذ ظَّلَمُواْ أَنفُسَهُمْ جَآؤُوكَ فَاسْتَغْفَرُواْ اللّهَ وَاسْتَغْفَرَ لَهُمُ الرَّسُولُ لَوَجَدُواْ اللّهَ تَوَّابًا رَّحِيمًا ﴾

“Had they, when they wronged themselves, come to you and pleaded Allah for forgiveness, and the Apostle had pleaded for forgiveness for them, they would have surely found Allah all-clement, all-merciful.”5
Elsewhere, the Qur’an quotes the sons of Ya‘qub (‘a) as saying:

"قالوا يأبانا استغفر لنا ذنوبنا إنا كُنا خطئين."

“They said, ‘Father! Plead {with Allah} for forgiveness of our sins! We have indeed been erring’.”6
So, Hadrat Ya‘qub (‘a) promised them to plead with Allah to forgive them without accusing them of polytheism (for asking him to plead for forgiveness):

قال سوف أستغفر لكم ربي إنه هو الغفور الرحيم.

“He said, ‘I shall plead with my Lord to forgive you; indeed He is the All-forgiving, the All-merciful’.”7

Notes
1. Surah az-Zumar 39:44.
2. Surah Sad 38:72-73.
3. Surah Yusuf 12:100.
4. Sunan Ibn Majah, vol. 2, “Bab Dhikr ash-Shafa‘ah,” p. 586.
5. Surah an-Nisa’ 4:64.
6. Surah Yusuf 12:97.
7. Surah Yusuf 12:98.