I'm creating a New Workflow Rules with existing field update, do I need to include the existing field update in ChangeSet?
Salesforce creates a record id for every record it uses, therefore the field update that you create will also get a record id.
However as you move to production to sandbox and back again you will be referencing different record id's. Salesforce also uses unique names for the field update records which can be referenced by the API.
As you copy your org to sandbox all records are recreated with new record id's, therefore if the workflow was to reference the field update by record id it would break.
Instead the workflow rule will use the unique name to call the field update and not the record id. That way you can maintain consistency of workflows moving form one org to another, or more specifically form sandbox to production.
This explanation should give you sufficient proof that you do NOT need to add the field update to the changeset.