If your PIC have an internal USART, sure it can work. I suggest you to download the PicMultiCalc and look what happen with the error % with different crystal speed
http://www.mister-e.org/pages/utilitiespag.html

@ 4MHz it's not going to be really accurate...