Translation:Can you give me a piece of paper?
"Can you give me a sheet of paper?" should be accepted as well, reported on Nov. 19, 2017.
May I have a piece of paper? There is no you in the sentence and keyi implies permission, so in English, it is proper to use "may I"
I don't think the 可以 is referring to 我 ("I") in this sentence. The 可以 applies to the 你 ("you"), which is implied but not explicitly included. This sentence is asking if the addressee can give the speaker (我) a piece of paper (hence the inclusion of the verb 给). I'm assuming "May I have a piece of paper" would be translated as 我可以有一张纸吗？.
You think too complicated.
In Chinese there's no difference between 可以給我張紙嗎 and 我可以有張紙嗎. It's just an expression. You discuss these it means you think with English logic instead of Chinese one.
If you wanna show more polite, then extend ur sentence is ok. 抱歉，可以給我張紙嗎 or 可以給我張紙好嗎.
Oh, okay. Sorry, I guess maybe I did sort of overthink it. In your example polite sentence, can you also say 对不起 instead of 抱歉?
Not really incorrect, but 對不起 is used when you did something bad and apologize. We seldom say 對不起 when you ask someone for something. 抱歉 or 不好意思 are both better here, like "excuse me".
Well, I'm Taiwanese, so I'm not familiar to Chinese using. They always think we speak too soft, like women whereas we think they speak too rude.