I am having a PCL with .Net 4.5 and Xamarin.Android target.
In .Net 4.5 System.Xml.Xsl exists and in the Xamarion.Android it exists too.
So why am I getting exceptions in a PCL project targeting these both Frameworks?
Support for each feature in a PCL needs to be added specifically to a PCL profile. It does not come automatically. Not every subset of selected platforms exists as PCL profile. You checked the platforms you were interested in and then Visual Studio choose one of the profiles it was compatible with. In this case the profile that includes Silverlight and iOS.
I am not sure if there is a PCL profile that supports System.Xml.Xsl.
An alternative is to use a shared project. In that case you are actually limited to the subset that is allowed by the referencing apps. This is what many users expect from a PCL. If you create Xamarin's template 'Blank App (Native Shared)' under 'Cross-Platform' and remove the WinPhone project (which does not support System.Xml.Xsl) you can use System.Xml.Xsl.