Is there a way to have a field with autocomplete values that are based on the input from another field? The values would be a result of previously entered data in the Channels (along with some other custom logic possibly). Is there an addon for this already? Or a native way to do this in EE?
Have you looked at the Suggest Field fieldtype? It uses previous values entered in the same field (previous entries), but it could be easily modified to look at another field instead.
That said, if you want to use an existing add-on then Playa could come close to what you need. It has autocomplete when using single-select mode. The multiple-select mode (called drop panes) has match-anywhere filtering using a search input built right into the field. And you have a lot of control over what channel entries are available in the field by pulling entries only from specific channels, statuses, authors, and/or categories.
Update: Even better, see the answer posted by Derek to check out the Suggest Field!