Truth is bitter, and many will find this hatred against him....just a warning for people who worship him.
Q1) Since When SaiBaba was incepted in Hindu Religion?
Well just after he started 'preaching' people, they were influenced by his magic, and miracles and people started blindly following him.
Quoting from this article, which uses a SaiBaba book and historical records for this speculation.
It is generally accepted that Sai Baba stayed in Shirdi for three years, disappeared for a year, and returned permanently around 1858.
So from this we can make an educated guess, and conclude that his influence(on 'Broad-minded' Hindus) started from(around) year 1858.
Q2) Is he Avatar of Lord Shiva or Lord Vishnu (Although none of the granthas talk about his incarnation/avatar) ?
Clearly NO! you've mentioned the reason yourself.
Worship of Sai Baba as a saint!
All of the vedanta followers(atleast Smarthas, Bhagwatas) would deny his worship because of the following reasons
1) He is preaching people without any qualification.
To qualify as an Acharya or just to initiate Vedic Studies you need to go through Upanayana ceremony which involves adhering to rules of Bramhacharya and wearing of Shikha(tuft)/Yagnopavitam.
Some people would say that even Shankaracharyas don't wear Yagnopavitam and Shikha, that is because they follow sanyasa order of Smartha sect(Advaita) for which they don't keep Shikha/Yagnopavitam, but still they have their Ekadanda.
He had no Yagnopavitam, never did he officially declare that he was an Acharya or even a Sanyasi. So there is no purpose or reason for his worship.
2) He never talked about getting Moksha for his people.
All acharyas are concerned about moksha of their shishyas, and they give them(shisyas) tips and tricks(methods) to attain moksha. Vedanta acharyas mainly focus on Upanishadic Bramha vidya and Bhakti marga for moksha.
Conclusion:
One should not disrespect Gods by associating random people as their incarnations in Bhuloka.
You can follow/Worship him if you want to but there is no use, at best he can make your life materially successful without moksha(which is eternal success).